Capacity of Clustered Distributed Storage

Abstract

A new system model reflecting the clustered structure of distributed storage is suggested to investigate interplay between storage overhead and repair bandwidth as storage node failures occur. Large data centers with multiple racks/disks or local networks of storage devices (e.g. sensor network) are good applications of the suggested clustered model. In realistic scenarios involving clustered storage structures, repairing storage nodes using intact nodes residing in other clusters is more bandwidth-consuming than restoring nodes based on information from intra-cluster nodes. Therefore, it is important to differentiate between intra-cluster repair bandwidth and cross-cluster repair bandwidth in modeling distributed storage. Capacity of the suggested model is obtained as a function of fundamental resources of distributed storage systems, namely, node storage capacity, intra-cluster repair bandwidth and cross-cluster repair bandwidth. The capacity is shown to be asymptotically equivalent to a monotonic decreasing function of number of clusters, as the number of storage nodes increases without bound. Based on the capacity expression, feasible sets of required resources which enable reliable storage are obtained in a closed-form solution. Specifically, it is shown that the cross-cluster traffic can be minimized to zero (i.e., intra-cluster local repair becomes possible) by allowing extra resources on storage capacity and intra-cluster repair bandwidth, according to the law specified in the closed-form. The network coding schemes with zero cross-cluster traffic are defined as intra-cluster repairable codes, which are shown to be a class of the previously developed locally repairable codes.

I Introduction

Many enterprises, including Google, Facebook, Amazon and Microsoft, use cloud storage systems in order to support massive amounts of data storage requests from clients. In the emerging Internet-of-Thing (IoT) era, the number of devices which generate data and connect to the network increases exponentially, so that efficient management of data center becomes a formidable challenge. However, since cloud storage systems are composed of inexpensive commodity disks, failure events occur frequently, degrading the system reliability [2].

In order to ensure reliability of cloud storage, distributed storage systems (DSSs) with erasure coding have been considered to improve tolerance against storage node failures [3, 4, 5, 6, 7, 8]. In such systems, the original file is encoded and distributed into multiple storage nodes. When a node fails, a newcomer node regenerates the failed node by contacting a number of survived nodes. This causes traffic burden across the network, taking up significant repair bandwidth. Earlier distributed storage systems utilized the 3-replication code: the original file was replicated three times, and the replicas were stored in three distinct nodes. The 3-replication coded systems require the minimum repair bandwidth, but incur high storage overhead. Reed-Solomon (RS) codes are also used (e.g. HDFS-RAID in Facebook [9]), which allow minimum storage overhead; however, RS-coded systems suffer from high repair bandwidth.

The pioneering work of [10] on distributed storage systems focused on the relationship between two required resources, the storage capacity $\alpha$ of each node and the repair bandwidth $\gamma$, when the system aims to reliably store a file $\mathcal{M}$ under node failure events. The optimal $(\alpha,\gamma)$ pairs are shown to have a fundamental trade-off relationship, to satisfy the maximum-distance-separable (MDS) property (i.e., any $k$ out of $n$ storage nodes can be accessed to recover the original file) of the system. Moreover, the authors of [10] obtained capacity $\mathcal{C}$, the maximum amount of reliably storable data, as a function of $\alpha$ and $\gamma$. The authors related the failure-repair process of a DSS with the multi-casting problem in network information theory, and exploited the fact that a cut-set bound is achievable by network coding [11]. Since the theoretical results of [10], explicit network coding schemes [12, 13, 14] which achieve the optimal $(\alpha,\gamma)$ pairs have also been suggested. These results are based on the assumption of homogeneous systems, i.e., each node has the same storage capacity and repair bandwidth.

However, in real data centers, storage nodes are dispersed into multiple clusters (in the form of disks or racks) [15, 7, 8], allowing high reliability against both node and rack failure events. In this clustered system, repairing a failed node gives rise to both intra-cluster and cross-cluster repair traffic. While the current data centers have abundant intra-rack communication bandwidth, cross-rack communication is typically limited. According to [16], nearly a $180$TB of cross-rack repair bandwidth is required everyday in the Facebook warehouse, limiting cross-rack communication for foreground map-reduce jobs. Moreover, surveys [17, 18, 19] on network traffic within data centers show that cross-rack communication is oversubscribed; the available cross-rack communication bandwidth is typically $5-20$ times lower than the intra-rack bandwidth in practical systems. Thus, a new system model which reflects the imbalance between intra- and cross-cluster repair bandwidths is required.

I-A Main Contributions

This paper suggests a new system model for clustered DSS to reflect the clustered nature of real distributed storage systems wherein an imbalance exists between intra- and cross-cluster repair burdens. This model can be applied to not only large data centers, but also local networks of storage devices such as the sensor networks or home clouds which are expected to be prevalent in the IoT era. This model is also more general in the sense that when the intra- and cross-cluster repair bandwidths are set to be equal, the resulting structure reduces to the original DSS model of [10]. This paper only considers recovering a single node failure at a time, as in [10]. The main contributions of this paper can be seen as twofold: one is the derivation of a closed-form expression for capacity, and the other is the analysis on feasible sets of system resources which enable reliable storage.

I-A1 Closed-form Expression for Capacity

Under the setting of functional repair, storage capacity $\mathcal{C}$ of the clustered DSS is obtained as a function of node storage capacity $\alpha$, intra-cluster repair bandwidth $\beta_{I}$ and cross-cluster repair bandwidth $\beta_{c}$. The existence of the cluster structure manifested as the imbalance between intra/cross-cluster traffics makes the capacity analysis challenging; Dimakis’ proof in [10] cannot be directly extended to handle the problem at hand. We show that symmetric repair (obtaining the same amount of information from each helper node) is optimal in the sense of maximizing capacity given the storage node size and total repair bandwidth, as also shown in [20] for the case of varying repair bandwidth across the nodes. However, we stress that in most practical scenarios, the need is greater for reducing cross-cluster communication burden, and we show that this is possible by trading with reduced overall storage capacity and/or increasing intra-repair bandwidth. Based on the derived capacity expression, we analyzed how the storage capacity $\mathcal{C}$ changes as a function of $L$, the number of clusters. It is shown that the capacity is asymptotically equivalent to $\underline{C}$, some monotonic decreasing function of $L$.

I-A2 Analysis on Feasible $(\alpha,\beta_{I},\beta_{c})$ Points

Given the need for reliably storing file $\mathcal{M}$, the set of required resource pairs, node storage capacity $\alpha$, intra-cluster repair bandwidth $\beta_{I}$ and cross-cluster repair bandwidth $\beta_{c}$, which enables $\mathcal{C}(\alpha,\beta_{I},\beta_{c})\geq\mathcal{M}$ is obtained in a closed-form solution. In the analysis, we introduce $\epsilon=\beta_{c}/\beta_{I}$, a useful parameter which measures the ratio of the cross-cluster repair burden (per node) to the intra-cluster burden. This parameter represents how scarce the available cross-cluster bandwidth is, compared to the abundant intra-cluster bandwidth. We here stress that the special case of $\epsilon=0$ corresponds to the scenario where repair is done only locally via intra-cluster communication, i.e., when a node fails the repair process requires intra-cluster traffic only without any cross-cluster traffic. Thus, the analysis on the $\epsilon=0$ case provides a guidance on the network coding for data centers for the scenarios where the available cross-cluster (cross-rack) bandwidth is very scarce.

Similar to the non-clustered case of [10], the required node storage capacity and the required repair bandwidth show a trade-off relationship. In the trade-off curve, two extremal points - the minimum-bandwidth-regenerating (MBR) point and the minimum-storage-regenerating (MSR) point - have been further analyzed for various $\epsilon$ values. Moreover, from the analysis on the trade-off curve, it is shown that the minimum storage overhead $\alpha=\mathcal{M}/k$ is achievable if and only if $\epsilon\geq\frac{1}{n-k}$. This implies that in order to reliably store file $\mathcal{M}$ with minimum storage $\alpha=\mathcal{M}/k$, sufficiently large cross-cluster repair bandwidth satisfying $\epsilon\geq\frac{1}{n-k}$ is required. Finally, for the scenarios with the abundant intra-cluster repair bandwidth, the minimum required cross-cluster repair bandwidth $\beta_{c}$ to reliably store file $\mathcal{M}$ is obtained as a function of node storage capacity $\alpha$.

I-B Related Works

Several researchers analyzed practical distributed storage systems with a goal in mind to reflect the non-homogeneous nature of storage nodes [20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]. A heterogeneous model was considered in [20, 21] where the storage capacity and the repair bandwidth for newcomer nodes are generally non-uniform. Upper/lower capacity bounds for the heterogeneous DSS are obtained in [20]. An asymmetric repair process is considered in [22], coining the terms, cheap and expensive nodes, based on the amount of data that can be transfered to any newcomer. The authors of [23] considered a flexible distributed storage system where the amount of information from helper nodes may be non-uniform, as long as the total repair bandwidth is bounded from above. The view points taken in these works are different from ours in that we adopt a notion of cluster and introduce imbalance between intra- and cross-cluster repair burdens.

Recently, some researchers considered the clustered structure of data centers [1, 24, 25, 26, 27, 28, 29, 30, 31]. Some recent works [24, 25, 26, 27] provided new system models for clustered DSS and shed light on fundamental aspects of the suggested system. In [24], the idea of [22] is developed to a two-rack system, by setting the communication burden within a rack much lower than the burden across different racks, similar to our analysis. However, the authors of [24] only considered systems with two racks, while the current paper considers a general setting of $L$ racks (clusters), and provides mathematical analysis on how the number of clusters (i.e., the dispersion of nodes) affects the capacity of clustered distributed storage. Similar to the present paper, the authors of [25, 26] obtained the capacity of clustered distributed storage, and provided capacity-achieving regenerating coding schemes. However, the coding schemes considered in [25, 26] do not satisfy the MDS property, and the capacity expression is obtained for limited scenarios when intra-cluster repair bandwidth $\beta_{I}$ is set to its maximum value. In contrast, the current paper provides the capacity expression for general values of $\beta_{I},\beta_{c}$ parameters, and analyzes the behavior of capacity as a function of the ratio $\epsilon=\beta_{c}/\beta_{I}$ between intra- and cross-cluster repair bandwidths. Moreover, unlike in the previous work, the capacity-achieving coding schemes (whose existence is shown) here satisfy the MDS property. In [27], the security issue in clustered distributed storage systems is considered, and the maximum amount of securely storable data in the existence of passive eavesdroppers is obtained.

There also have been some recent works [28, 29, 30, 31] on network code design appropriate for clustered distributed storage. Motivated by the limited available cross-rack repair bandwidth in real data centers, the work of [28] provides a network coding scheme which minimizes the cross-rack bandwidth in clustered distributed storage systems. However, the suggested coding scheme is applicable for some limited $(n,k,L)$ parameters and the minimum storage overhead ($\alpha=\mathcal{M}/k$) setting. On the other hand, the current paper provides the capacity expression for general $(n,k,L,\alpha)$ setting, and proves the existence of capacity-achieving coding scheme. The authors of [29] proposed coding schemes tolerant to rack failure events in multi-rack storage systems, but have not addressed the imbalance between intra- and cross-cluster repair burdens in node failure events, which is an important aspect of the current paper. The authors of [30] considers the scenario of having grouped (clustered) storage nodes where nodes in the same group are more accessible to each other, compared to the nodes in other groups. However, the focus is different to the present paper: [30] focuses on the code construction which has the minimum amount of accessed data (called the optimal access property), while the scope of the present paper is on finding the optimal trade-off between the node storage capacity and the repair bandwidth, as a function of the ratio $\epsilon$ of intra- and cross-cluster communication burdens. Finally, a locally repairable code which can repair arbitrary node within each group is suggested in [31]; this code can suppress the inter-group repair bandwidth to zero. However, the coding scheme is suggested for the $\epsilon=0$ case only, while the present paper provides the capacity expression for general $0\leq\epsilon\leq 1$, and proves the existence of an optimal coding scheme.

Compared to the conference version [1] of the current work, this paper provides the formal proofs for the capacity expression, and obtains the feasible $(\alpha,\gamma)$ region for $0\leq\epsilon\leq 1$ setting (only $\epsilon=0$ is considered in [1]). The present paper also shows the behavior of capacity as a function of $L$, the number of clusters, and provides the sufficient and necessary conditions on $\epsilon=\beta_{c}/\beta_{I}$, to achieve the minimum storage overhead $\alpha=\mathcal{M}/k$. Finally, the asymptotic behaviors of the MBR/MSR points are investigated in this paper, and the connection between what we call the intra-cluster repairable codes and the existing locally repairable codes [32] is revealed.

I-C Organization

This paper is organized as follows. Section II reviews preliminary materials about distributed storage systems and the information flow graph, an efficient tool for analyzing DSS. Section III proposes a new system model for the clustered DSS, and derives a closed-form expression for the storage capacity of the clustered DSS. The behavior of the capacity curves is also analyzed in this section. Based on the capacity expression, Section IV provides results on the feasible resource pairs which enable reliable storage of a given file. Further research topics on clustered DSS are discussed in Section V, and Section VI draws conclusions.

II Background

II-A Distributed Storage System

Distributed storage systems can maintain reliability by means of erasure coding [33]. The original data file is spread into $n$ potentially unreliable nodes, each with storage size $\alpha$. When a node fails, it is regenerated by contacting $d<n$ helper nodes and obtaining a particular amount of data, $\beta$, from each helper node. The amount of communication burden imposed by one failure event is called the repair bandwidth, denoted as $\gamma=d\beta$. When the client requests a retrieval of the original file, assuming all failed nodes have been repaired, access to any $k<n$ out of $n$ nodes must guarantee a file recovery. The ability to recover the original data using any $k<n$ out of $n$ nodes is called the maximal-distance-separable (MDS) property. Distributed storage systems can be used in many applications such as large data centers, peer-to-peer storage systems and wireless sensor networks [10].

II-B Information Flow Graph

Information flow graph is a useful tool to analyze the amount of information flow from source to data collector in a DSS, as utilized in [10]. It is a directed graph consisting of three types of nodes: data source $\mathrm{S}$, data collector $\mathrm{DC}$, and storage nodes $x^{i}$ as shown in Fig. 1. Storage node $x^{i}$ can be viewed as consisting of input-node $x_{in}^{i}$ and output-node $x_{out}^{i}$, which are responsible for the incoming and outgoing edges, respectively. $x_{in}^{i}$ and $x_{out}^{i}$ are connected by a directed edge with capacity identical to the storage size $\alpha$ of node $x^{i}$.

Data from source $S$ is stored into $n$ nodes. This process is represented by $n$ edges going from $\mathrm{S}$ to $\{x^{i}\}_{i=1}^{n}$, where each edge capacity is set to infinity. A failure/repair process in a DSS can be described as follows. When a node $x^{j}$ fails, a new node $x^{n+1}$ joins the graph by connecting edges from $d$ survived nodes, where each edge has capacity $\beta$. After all repairs are done, data collector $\mathrm{DC}$ chooses arbitrary $k$ nodes to retrieve data, as illustrated by the edges connected from $k$ survived nodes with infinite edge capacity. Fig. 1 gives an example of information flow graph representing a distributed storage system with $n=4,k=3,d=3$.

Figure 1: Information flow graph ($n=4,k=3,d=3$)

Figure 2: Clustered distributed storage system ($n=15,L=3$)

II-C Notation used in the paper

This paper requires many notations related to graphs, because it deals with information flow graphs. Here we provide the definition of each notation used in the paper. For the given system parameters, we denote $\mathcal{G}$ as the set of all possible information flow graphs. A graph $G\in\mathcal{G}$ is denoted as $G=(V,E)$ where $V$ is the set of vertices and $E$ is the set of edges in the graph. For a given graph $G\in\mathcal{G}$, we call a set $c\subset E$ of edges as cut-set [34] if it satisfies the following: every directed path from $\mathrm{S}$ to $\mathrm{DC}$ includes at least one edge in $c$. An arbitrary cut-set $c$ is usually denoted as $c=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ where $U\subset V$ and $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu=V\setminus U$ (the complement of $U$) satisfy the following: the set of edges from $U$ to $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$ is the given cut-set $c$. The set of all cut-sets available in $G$ is denoted as $C(G)$. For a graph $G\in\mathcal{G}$ and a cut-set $c\in C(G)$, we denote the sum of edge capacities for edges in $c$ as $w(G,c)$, which is called the cut-value of $c$.

A vector is denoted as v using the bold notation. For a vector v, the transpose of the vector is denoted as $\textbf{v}^{T}$. A set is denoted as $X=\{x_{1},x_{2},\cdots,x_{k}\}$, while a sequence $x_{1},x_{2},\cdots,x_{N}$ is denoted as $(x_{n})_{n=1}^{N}$, or simply $(x_{n})$. For given sequences $(a_{n})$ and $(b_{n})$, we use the term “$a_{n}$ is asymptotically equivalent to $b_{n}$” [35] if and only if

$$\lim\limits_{n\rightarrow\infty}\frac{a_{n}}{b_{n}}=1.$$ (1)

We utilize a useful notation:

$$\mathds{1}_{i=j}=\begin{cases}1,&\text{ if }i=j\\ 0,&\text{ otherwise.}\end{cases}$$

For a positive integer $n$, we use $[n]$ as a simplified notation for the set $\{1,2,\cdots,n\}$. For a non-positive integer $n$, we define $[n]=\emptyset$. Each storage node is represented as either $x^{t}=(x_{in}^{t},x_{out}^{t})$ as defined in Section II-B, or $N(i,j)$ as defined in (A.2). Finally, important parameters used in this paper are summarized in Table I.

TABLE I: Parameters used in this paper

$n$	number of storage nodes
$k$	number of DC-contacting nodes
$L$	number of clusters
$n_{I}=n/L$	number of nodes in a cluster
$d_{I}=n_{I}-1$	number of intra-cluster helper nodes
$d_{c}=n-n_{I}$	number of cross-cluster helper nodes
$\mathbb{F}_{q}$	base field which contains each symbol
$\alpha$	storage capacity of each node
$\beta_{I}$	intra-cluster repair bandwidth (per node)
$\beta_{c}$	cross-cluster repair bandwidth (per node)
$\gamma_{I}=d_{I}\beta_{I}$	intra-cluster repair bandwidth
$\gamma_{c}=d_{c}\beta_{c}$	cross-cluster repair bandwidth
$\gamma=\gamma_{I}+\gamma_{c}$	repair bandwidth
$\epsilon=\beta_{c}/\beta_{I}$	ratio of $\beta_{c}$ to $\beta_{I}$ ($0\leq\epsilon\leq 1$)
$\xi=\gamma_{c}/\gamma$	ratio of $\gamma_{c}$ to $\gamma$ ($0\leq\xi<1$)
$R=k/n$	ratio of $k$ to $n$ ($0<R\leq 1$)

III Capacity of Clustered DSS

III-A Clustered Distributed Storage System

A distributed storage system with multiple clusters is shown in Fig. 2. Data from source $\mathrm{S}$ is stored at $n$ nodes which are grouped into $L$ clusters. The number of nodes in each cluster is fixed and denoted as $n_{I}=n/L$. The storage size of each node is denoted as $\alpha$. When a node fails, a newcomer node is regenerated by contacting $d_{I}$ helper nodes within the same cluster, and $d_{c}$ helper nodes from other clusters. This paper considers functional repair[33] in the regeneration process; the newcomer node may store different content from that of the failed node, while maintaining the MDS property of the code. The amount of data a newcomer node receives within the same cluster is $\gamma_{I}=d_{I}\beta_{I}$ (each node equally contributes to $\beta_{I}$), and that from other clusters is $\gamma_{c}=d_{c}\beta_{c}$ (each node equally contributes to $\beta_{c}$). Fig. 3 illustrates an example of information flow graph representing the repair process in a clustered DSS.

Figure 3: Repair process in clustered DSS ($n=4,L=2,d_{I}=1,d_{c}=2$)

III-B Assumptions for the System

We assume that $d_{c}$ and $d_{I}$ have the maximum possible values ($d_{c}=n-n_{I},d_{I}=n_{I}-1$), since this is the capacity-maximizing choice, as formally stated in the following proposition. The proof of the proposition is in Appendix G-A.

Proposition 1.

Consider a clustered distributed storage system with given $\gamma$ and $\gamma_{c}$. Then, setting both $d_{I}$ and $d_{c}$ to their maximum values maximizes storage capacity.

Note that the authors of [10] already showed that in the non-clustered scenario with given repair bandwidth $\gamma$, maximizing the number of helper nodes $d$ is the capacity-maximizing choice. Here, we are saying that a similar property also holds for clustered scenario considered in the present paper. Under the setting of the maximum number of helper nodes, the overall repair bandwidth for a failure event is denoted as

$$\gamma=\gamma_{I}+\gamma_{c}=(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}$$ (2)

Data collector $\mathrm{DC}$ contacts any $k$ out of $n$ nodes in the clustered DSS. Given that the typical intra-cluster communication bandwidth is larger than the cross-cluster bandwidth in real systems, we assume

$$\beta_{I}\geq\beta_{c}$$

throughout the present paper; this assumption limits our interest to $\epsilon\leq 1$. Moreover, motivated by the security issue, we assume that a file cannot be retrieved entirely by contacting any single cluster having $n_{I}$ nodes. Thus, the number $k$ of nodes contacted by the data collector satisfies

$$k >n_{I}.$$ (3)

We also assume

$$L\geq 2$$ (4)

which holds for most real DSSs. Usually, all storage nodes cannot be squeezed in a single cluster, i.e., $L=1$ rarely happens in practical systems, to prevent losing everything when the cluster is destroyed. Note that many storage systems [7, 8, 16] including those of Facebook uses $L=n$, i.e., every storage node reside in different racks (clusters), to tolerate the rack failure events. Finally, according to [16], nearly $98\%$ of data recoveries in real systems deal with single node recovery. In other words, the portion of simultaneous multiple nodes failure events is small. Therefore, the present paper focuses single node failure events.

III-C The closed-form solution for Capacity

Consider a clustered DSS with fixed $n,k,L$ values. In this model, we want to find the set of feasible parameters ($\alpha,\beta_{I},\beta_{c}$) which enables storing data of size $\mathcal{M}$. In order to find the feasible set, min-cut analysis on the information flow graph is required, similar to [10]. Depending on the failure-repair process and $k$ nodes contacted by $\mathrm{DC}$, various information flow graphs can be obtained.

Let $\mathcal{G}$ be the set of all possible flow graphs. Consider a graph $G^{*}\in\mathcal{G}$ with minimum min-cut, the construction of which is specified in Appendix A. Based on the max-flow min-cut theorem in [11], the maximum information flow from source to data collector for arbitrary $G\in\mathcal{G}$ is greater than or equal to

$$\mathcal{C}(\alpha,\beta_{I},\beta_{c})\coloneqq\text{min-cut of }G^{*},$$

which is called the capacity of the system. In order to send data $\mathcal{M}$ from the source to the data collector, $\mathcal{C}\geq\mathcal{M}$ should be satisfied. Moreover, if $\mathcal{C}\geq\mathcal{M}$ is satisfied, there exists a linear network coding scheme [11] to store a file with size $\mathcal{M}$. Therefore, the set of $(\alpha,\beta_{I},\beta_{c})$ points which satisfies $\mathcal{C}\geq\mathcal{M}$ is feasible in the sense of reliably storing the original file of size $\mathcal{M}$. Now, we state our main result in the form of a theorem which offers a closed-form solution for the capacity $\mathcal{C}(\alpha,\beta_{I},\beta_{c})$ of the clustered DSS. Note that setting $\beta_{I}=\beta_{c}$ reduces to capacity of the non-clustered DSS obtained in [10].

Theorem 1.

The capacity of the clustered distributed storage system with parameters $(n,k,L,\alpha,\beta_{I},\beta_{c})$ is

$$\mathcal{C}(\alpha,\beta_{I},\beta_{c})=\sum_{i=1}^{n_{I}}\sum_{j=1}^{g_{i}}\min\{\alpha,\rho_{i}\beta_{I}+(n-\rho_{i}-j-\sum_{m=1}^{i-1}g_{m})\beta_{c}\},$$ (5)

where

$$\rho_{i} =n_{I}-i,$$ (6)

$$g_{m} =\begin{cases}\lfloor\frac{k}{n_{I}}\rfloor+1,&m\leq(k\ \mathrm{mod}\ n_{I})\\ \lfloor\frac{k}{n_{I}}\rfloor,&otherwise.\end{cases}$$ (7)

The proof is in Appendix A. Note that the parameters used in the statement of Theorem 1 have the following property, the proof of which is in Appendix G-B.

Proposition 2.

For every $(i,j)$ with $i\in[n_{I}],j\in[g_{i}]$, we have

$$\rho_{i}\beta_{I}+(n-\rho_{i}-j-\sum_{m=1}^{i-1}g_{m})\beta_{c}\leq\gamma.$$ (8)

Moreover,

$$\sum_{m=1}^{n_{I}}g_{m}=k$$ (9)

holds.

III-D Relationship between $\mathcal{C}$ and $\epsilon=\beta_{c}/\beta_{I}$

In this subsection, we analyze the capacity of a clustered DSS as a function of an important parameter

$$\epsilon\coloneqq\beta_{c}/\beta_{I},$$ (10)

the cross-cluster repair burden per intra-cluster repair burden. In Fig. 4, capacity is plotted as a function of $\epsilon$. From (2), the total repair bandwidth can be expressed as

$$\gamma =\gamma_{I}+\gamma_{c}=(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}$$

$$=\Big{(}n_{I}-1+(n-n_{I})\epsilon\Big{)}\beta_{I}.$$ (11)

Using this expression, the capacity is expressed as

$$\mathcal{C}(\epsilon)=\sum_{i=1}^{n_{I}}\sum_{j=1}^{g_{i}}\min\Big{\{}\alpha,\frac{(n-\rho_{i}-j-\sum_{m=1}^{i-1}g_{m})\epsilon+\rho_{i}}{(n-n_{I})\epsilon+n_{I}-1}\gamma\Big{\}}.$$ (12)

For fair comparison on various $\epsilon$ values, capacity is calculated for a fixed ($n,k,L,\alpha,\gamma$) set. The capacity is an increasing function of $\epsilon$ as shown in Fig. 4. This implies that for given resources $\alpha$ and $\gamma$, allowing a larger $\beta_{c}$ (until it reaches $\beta_{I}$) is always beneficial, in terms of storing a larger file. For example, under the setting in Fig. 4, allowing $\beta_{c}=\beta_{I}$ (i.e., $\epsilon=1$) can store $\mathcal{M}=48$, while setting $\beta_{c}=0$ (i.e., $\epsilon=0$) cannot achieve the same level of storage. This result is consistent with the previous work on asymmetric repair in [20], which proved that the symmetric repair maximizes capacity. Therefore, when the total communication amount $\gamma$ is fixed, a loss of storage capacity is the cost we need to pay in order to reduce the communication burden $\beta_{c}$ across different clusters.

Figure 4: Capacity as a function of $\epsilon$, under the setting of $n=100,k=85,L=10,\alpha=1,\gamma=1$

III-E Relationship between $\mathcal{C}$ and $L$

In this subsection, we analyze the capacity of a clustered DSS as a function of $L$, the number of clusters. For fair comparison, ($n,k,\alpha,\gamma$) values are fixed for calculating capacity. In Fig. 5, capacity curves for two scenarios are plotted over a range of $L$ values. First, the solid line corresponds to the scenario when the system has abundant cross-rack bandwidth resources $\gamma_{c}$. In this ideal scenario which does not suffer from the over-subscription problem, the system can store $\mathcal{M}=80$ irrespective of the dispersion of nodes.

However, consider a practical situation where the available cross-rack bandwidth is scarce compared to the intra-rack bandwidth; for example, $\xi=\gamma_{c}/\gamma=1/5$. The dashed line in Fig. 5 corresponds to this scenario where the system has not enough cross-rack bandwidth resources. In this practical scenario, reducing $L$ (i.e., gathering the storage nodes into a smaller number of clusters) increases capacity. However, note that sufficient dispersion of data into a fair number of clusters is typically desired, in order to guarantee the reliability of storage in rack-failure events. Finding the optimal number $L^{*}$ of clusters in this trade-off relationship remains as an important topic for future research.

Figure 5: Capacity as a function of $L$, under the setting of $n=100,k=80,\alpha=1,\gamma=10$

Figure 6: An example of DSS with dispersion ratio $\sigma=5/3$, when the parameters are set to $L=3,n_{I}=5,n=n_{I}L=15$

In Fig. 5, the capacity is a monotonic decreasing function of $L$ when the system suffers from an over-subscription problem. However, in general $(n,k,\alpha,\gamma)$ parameter settings, capacity is not always a monotonic decreasing function of $L$. Theorem 2 illustrates the behavior of capacity as $L$ varies, focusing on the special case of $\gamma=\alpha.$ Before formally stating the next main result, we need to define

$$\sigma\coloneqq\frac{L}{n_{I}}=\frac{L^{2}}{n},$$ (13)

the dispersion factor of a clustered storage system, as illustrated in Fig. 6. In the two-dimensional representation of a clustered distributed storage system, $L$ represents the number of rows (clusters), while $n_{I}=n/L$ represents the number of columns (nodes in each cluster). The dispersion factor $\sigma$ is the ratio of the number of rows to the number of columns. If $L$ increases for a fixed $n_{I}$, then $\sigma$ grows and the nodes become more dispersed into multiple clusters.

Now we state our second main result, which is about the behavior of $\mathcal{C}$ versus $L$.

Theorem 2.

Consider the $\gamma=\alpha$ case when $\sigma,\gamma,R$ and $\xi$ are fixed. In the asymptotic regime of large $n$, capacity $\mathcal{C}(\alpha,\beta_{I},\beta_{c})$ is asymptotically equivalent to

$$\underline{C}=\frac{k}{2}\left(\gamma+\frac{n-k}{n(1-1/L)}\gamma_{c}\right),$$ (14)

a monotonically decreasing function of $L$. This can also be stated as

$$\mathcal{C}\sim\underline{C}$$ (15)

as $n\rightarrow\infty$ for a fixed $\sigma$.

Note that under the setting of Theorem 2, we have

$$n_{I} =\frac{n}{L}=\frac{n}{\sqrt{n\sigma}}=\Theta(\sqrt{n}),$$

$$k =nR=\Theta(n),\quad\alpha=\gamma=\text{constant},$$

$$\beta_{I} =\frac{\gamma_{I}}{n_{I}-1}=\Theta(\frac{1}{\sqrt{n}}),\quad\beta_{c}=\frac{\gamma_{c}}{n-n_{I}}=\Theta(\frac{1}{n})$$

in the asymptotic regime of large $n$. The proof of Theorem 2 is based on the following two lemmas.

Lemma 1.

In the case of $\gamma=\alpha$, capacity $\mathcal{C}(\alpha,\beta_{I},\beta_{c})$ is upper/lower bounded as

$$\underline{C}\leq\mathcal{C}(\alpha,\beta_{I},\beta_{c})\leq\underline{C}+\delta$$ (16)

where

$$\delta =n_{I}^{2}(\beta_{I}-\beta_{c})/8$$ (17)

and $\underline{C}$ is defined in (14).

Lemma 2.

In the case of $\gamma=\alpha$, $\underline{C}$ and $\delta$ defined in (14), (17) satisfy

$$\underline{C} =\Theta(n),$$

$$\delta =O(n_{I})$$

when $\gamma,R$ and $\xi$ are fixed.

The proofs of these lemmas are in Appendix H. Here we provide the proof of Theorem 2 by using Lemmas 1 and 2.

proof (of Theorem 2).

From Lemma 2,

$$\delta/\underline{C}=O(1/L)=O(\sqrt{1/n\sigma})\rightarrow 0$$ (18)

as $n\rightarrow\infty$ for a fixed $\sigma$. Moreover, dividing (16) by $\underline{C}$ results in

$$1\leq\mathcal{C}/\underline{C}\leq 1+\delta/\underline{C}.$$ (19)

Putting (18) into (19) completes the proof. ∎

IV Discussion on Feasible ($\alpha,\beta_{I},\beta_{c}$)

In the previous section, we obtained the capacity of the clustered DSS. This section analyzes the feasible ($\alpha,\beta_{I},\beta_{c}$) points which satisfy $\mathcal{C}(\alpha,\beta_{I},\beta_{c})\geq\mathcal{M}$ for a given file size $\mathcal{M}$. Using

$$\gamma=\gamma_{I}+\gamma_{c}=(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}$$

in (2), the behavior of the feasible set of $(\alpha,\gamma)$ points can be observed. Essentially, the feasible points demonstrate a trade-off relationship. Two extreme points – minimum storage regenerating (MSR) point and minimum bandwidth regenerating (MBR) point – of the trade-off has been analyzed. Moreover, a special family of network codes which satisfy $\epsilon=0$, which we call the intra-cluster repairable codes, is compared with the locally repairable codes considered in [32]. Finally, the set of feasible $(\alpha,\beta_{c})$ points is discussed, when the system allows maximum $\beta_{I}$.

IV-A Set of Feasible $(\alpha,\gamma)$ Points

We provide a closed-form solution for the set of feasible $(\alpha,\gamma)$ points which enable reliable storage of data $\mathcal{M}$. Based on the range of $\epsilon$ defined in (10), the set of feasible points show different behaviors as stated in Corollary 1.

Corollary 1.

Consider a clustered DSS for storing data $\mathcal{M}$, when $\epsilon=\beta_{c}/\beta_{I}$ satisfies $0\leq\epsilon\leq 1$. For any $\gamma\geq\gamma^{*}(\alpha)$, the data $\mathcal{M}$ can be reliably stored, i.e., $\mathcal{C}\geq\mathcal{M}$, while it is impossible to reliably store data $\mathcal{M}$ when $\gamma<\gamma^{*}(\alpha)$. The threshold function $\gamma^{*}(\alpha)$ can be obtained as:

1. if $\frac{1}{n-k}\leq\epsilon\leq 1$

   $$\gamma^{*}(\alpha)=\begin{cases}\infty,&\ \alpha\in(0,\frac{M}{k})\\ \frac{M-t\alpha}{s_{t}},&\ \alpha\in[\frac{M}{t+1+s_{t+1}y_{t+1}},\frac{M}{t+s_{t}y_{t}}),\\ &\ \ \ \ \ \ \ \ \ \ (t=k-1,k-2,\cdots,1)\\ \frac{M}{s_{0}},&\ \alpha\in[\frac{M}{s_{0}},\infty)\end{cases}$$ (20)

2. Otherwise (if $0\leq\epsilon<\frac{1}{n-k}$)

   $$\gamma^{*}(\alpha)=\begin{cases}\infty,&\ \alpha\in(0,\frac{M}{\tau+\sum_{i=\tau+1}^{k}z_{i}})\\ \frac{\mathcal{M}-\tau\alpha}{s_{\tau}},&\ \alpha\in[\frac{M}{\tau+\sum_{i=\tau+1}^{k}z_{i}},\frac{\mathcal{M}}{\tau+s_{\tau}y_{\tau}})\\ \frac{M-t\alpha}{s_{t}},&\ \alpha\in[\frac{M}{t+1+s_{t+1}y_{t+1}},\frac{M}{t+s_{t}y_{t}}),\\ &\ \ \ \ \ \ \ \ \ \ (t=\tau-1,\tau-2,\cdots,1)\\ \frac{M}{s_{0}},&\ \alpha\in[\frac{M}{s_{0}},\infty)\end{cases}$$ (21)

where

$$\tau =\max\{t\in\{0,1,\cdots,k-1\}:z_{t}\geq 1\}$$ (22)

$$s_{t} =\begin{cases}\frac{\sum_{i=t+1}^{k}z_{i}}{(n_{I}-1)+\epsilon(n-n_{I})},&t=0,1,\cdots,k-1\\ 0,&t=k\end{cases}$$ (23)

$$y_{t} =\frac{(n_{I}-1)+\epsilon(n-n_{I})}{z_{t}},$$ (24)

$$z_{t} =\begin{cases}(n-n_{I}-t+h_{t})\epsilon+(n_{I}-h_{t}),&t\in[k]\\ \infty,&t=0\end{cases}$$ (25)

$$h_{t} =\min\{s\in[n_{I}]:\sum_{l=1}^{s}g_{l}\geq t\},$$ (26)

and $\{g_{l}\}_{l=1}^{n_{I}}$ is defined in (7).

Figure 7: Optimal tradeoff between node storage size $\alpha$ and total repair bandwidth $\gamma$, under the setting of $n=15,k=8,L=3,\mathcal{M}=8$

Figure 8: Optimal tradeoff between node storage size $\alpha$ and cross-rack repair bandwidth $\gamma_{c}$, under the setting of $n=15,k=8,L=3,\mathcal{M}=8$

An example for the trade-off results of Corollary 1 is illustrated in Fig. 7, for various $0\leq\epsilon\leq 1$ values. Here, the $\epsilon=1$ (i.e., $\beta_{I}=\beta_{c}$) case corresponds to the symmetric repair in the non-clustered scenario [10]. The plot for $\epsilon=0$ (or $\beta_{c}=\gamma_{c}=0$) shows that the cross-cluster repair bandwidth can be reduced to zero with extra resources ($\alpha$ or $\gamma_{I}$), where the amount of required resources are specified in Corollary 1. Note that in the case of $\epsilon=0$, the storage system is completely localized, i.e., nodes can be repaired exclusively from their cluster. From Fig. 7, we can confirm that as $\epsilon$ decreases, extra resources ($\gamma$ or $\alpha$) are required to reliably store the given data $\mathcal{M}$. Moreover, Corollary 1 suggests a mathematically interesting result, stated in the following Theorem, the proof of which is in Appendix B.

Theorem 3.

A clustered DSS can reliably store file $\mathcal{M}$ with the minimum storage overhead $\alpha=\mathcal{M}/k$ if and only if

$$\epsilon\geq\frac{1}{n-k}.$$ (27)

Note that $\alpha=\mathcal{M}/k$ is the minimum storage overhead which can satisfy the MDS property, as stated in [10]. The implication of Theorem 3 is shown in Fig. 7. Under the $\mathcal{M}=k=8$ setting, data $\mathcal{M}$ can be reliably stored with minimum storage overhead $\alpha=\mathcal{M}/k=1$ for $\frac{1}{n-k}\leq\epsilon\leq 1$, while it is impossible to achieve minimum storage overhead $\alpha=\mathcal{M}/k=1$ for $0\leq\epsilon<\frac{1}{n-k}$. Finally, since reducing the cross-cluster repair burden $\gamma_{c}$ is regarded as a much harder problem compared to reducing the intra-cluster repair burden $\gamma_{I}$, we also plotted feasible $(\alpha,\gamma_{c})$ pairs for various $\epsilon$ values in Fig. 8. The plot for $\epsilon=0$ obviously has zero $\gamma_{c}$, while $\epsilon>0$ cases show a trade-off relationship. As $\epsilon$ increases, the minimum $\gamma_{c}$ value increases gradually.

IV-B Minimum-Bandwidth-Regenerating (MBR) point and Minimum-Storage-Regenerating (MSR) point

Figure 9: Set of Feasible $(\alpha,\gamma)$ Points

According to Corollary 1, the set of feasible $(\alpha,\gamma)$ points shows a trade-off curve as in Fig. 9, for arbitrary $n,k,L,\epsilon$ settings. Here we focus on two extremal points: the minimum-bandwidth-regenerating (MBR) point and the minimum-storage-regenerating (MSR) point. As originally defined in [10], we call the point on the trade-off with minimum bandwidth $\gamma$ as MBR. Similarly, we call the point with minimum storage $\alpha$ as MSR. Let $(\alpha_{msr}^{(\epsilon)},\gamma_{msr}^{(\epsilon)})$ be the $(\alpha,\gamma)$ pair of the MSR point for given $\epsilon$. Similarly, define $(\alpha_{mbr}^{(\epsilon)},\gamma_{mbr}^{(\epsilon)})$ as the parameter pair for MBR points. According to Corollary 1, the explicit $(\alpha,\gamma)$ expression for the MSR and MBR points are as in the following Corollary, the proof of which is given in Appendix F-B.

Corollary 2.

For a given $0\leq\epsilon\leq 1$, we have

$$(\alpha_{msr}^{(\epsilon)},\gamma_{msr}^{(\epsilon)})$$

$$=\begin{cases}(\frac{\mathcal{M}}{\tau+\sum_{i=\tau+1}^{k}z_{i}},\frac{\mathcal{M}}{\tau+\sum_{i=\tau+1}^{k}z_{i}}\frac{\sum_{i=\tau+1}^{k}z_{i}}{s_{\tau}}),&0\leq\epsilon<\frac{1}{n-k}\\ (\frac{\mathcal{M}}{k},\frac{\mathcal{M}}{k}\frac{1}{s_{k-1}}),&\frac{1}{n-k}\leq\epsilon\leq 1\end{cases}$$ (28)

$$(\alpha_{mbr}^{(\epsilon)},\gamma_{mbr}^{(\epsilon)}) =(\frac{\mathcal{M}}{s_{0}},\frac{\mathcal{M}}{s_{0}}).$$ (29)

Now we compare the MSR and MBR points for two extreme cases of $\epsilon=0$ and $\epsilon=1$. Using $R\coloneqq k/n$ and the dispersion ratio $\sigma$ defined in (13), the asymptotic behaviors of MBR and MSR points are illustrated in the following theorem, the proof of which is in Appendix C.

Theorem 4.

Consider the MSR point $(\alpha_{msr}^{(\epsilon)},\gamma_{msr}^{(\epsilon)})$ and the MBR point $(\alpha_{mbr}^{(\epsilon)},\gamma_{mbr}^{(\epsilon)})$ for $\epsilon=0,1$. The minimum node storage for $\epsilon=0$ is asymptotically equivalent to the minimum node storage for $\epsilon=1$, i.e.,

$$\alpha_{msr}^{(0)}\sim\alpha_{msr}^{(1)}=\mathcal{M}/k$$ (30)

as $n\rightarrow\infty$ for arbitrary fixed $\sigma$ and $R=k/n$. Moreover, the MBR point for $\epsilon=0$ approaches the MBR point for $\epsilon=1$, i.e.,

$$(\alpha_{mbr}^{(0)},\gamma_{mbr}^{(0)})\rightarrow(\alpha_{mbr}^{(1)},\gamma_{mbr}^{(1)}),$$ (31)

as $R=k/n\rightarrow 1$. The ratio between $\gamma_{mbr}^{(0)}$ and $\gamma_{mbr}^{(1)}$ is expressed as

$$\frac{\gamma_{mbr}^{(0)}}{\gamma_{mbr}^{(1)}}\leq 2-\frac{k-1}{n-1}$$ (32)

Figure 10: Optimal trade-off curves for $\epsilon=0,1$

Note that under the setting of Theorem 4, we have

$$\alpha_{msr}^{(1)} =\text{constant},\quad k=nR=\Theta(n),\quad\mathcal{M}=\Theta(n)$$

in the asymptotic regime of large $n$. According to Theorem 4, the minimum storage for $\epsilon=0$ can achieve $\mathcal{M}/k$ as $n\rightarrow\infty$ with fixed $R=k/n$. This result coincides with the result of Theorem 3. According to Theorem 3, the sufficient and necessary condition for achieving the minimum storage of $\alpha=\mathcal{M}/k$ is

$$\epsilon\geq\frac{1}{n-k}=\frac{1}{n(1-R)}.$$ (33)

As $n$ increases with a fixed $R$, the lower bound on $\epsilon$ reduces, so that in the asymptotic regime, $\epsilon=0$ can achieve $\alpha=\mathcal{M}/k$.

(a)

(b)

Figure 11: MBR coding schemes for $n=6,k=5,L=2,\alpha=10$ [sub-symbol], $\gamma=10$ [sub-symbol]

Moreover, Theorem 4 states that the MBR point for $\epsilon=0$ approaches the MBR point for $\epsilon=1$ as $R=k/n$ goes to 1. Fig. 11 provides two MBR coding schemes with $(n,k,L)=(6,5,2)$, which has different $\epsilon$ values; one coding scheme in Fig. 11a satisfies $\epsilon=1$, while the other in Fig. 11b satisfies $\epsilon=0$. The RSKR coding scheme [12] is applied to the six nodes in Fig. 11a. Each node (illustrated as a rectangular box) contains five $c_{i}$ symbols, where each symbol $c_{i}$ consists of two sub-symbols, $c_{i}^{(1)}$ and $c_{i}^{(2)}$. Note that any symbol $c_{i}$ is shared by exactly two nodes in Fig. 11a, which is due to the property of RSKR coding. This system can reliably store fifteen symbols $\{c_{i}\}_{i=1}^{15}$, or $\mathcal{M}=30$ sub-symbols $\{c_{i}^{(1)},c_{i}^{(2)}\}_{i=1}^{15}$, since it satisfies two properties – the exact repair property and the data recovery property – as illustrated below. First, when a node fails, five other nodes transmit five symbols (one distinct symbol by each node), which exactly regenerates the failed node. Second, we can retrieve data, $\mathcal{M}=30$ sub-symbols $\{c_{i}^{(1)},c_{i}^{(2)}\}_{i=1}^{15}$, by contacting any $k=5$ nodes. In Fig. 11b, each node contains two $e_{i}$ symbols, where each symbol $e_{i}$ consists of five sub-symbols, $\{e_{i}^{(j)}\}_{j=1}^{5}$. Note that in Fig. 11b, any symbol $e_{i}$ is shared by exactly two nodes which reside in the same cluster. This is because we applied RSKR coding at each cluster in the system of Fig. 11b. This system can reliably store six symbols $\{e_{i}\}_{i=1}^{6}$, or $\mathcal{M}=30$ sub-symbols $\bigcup_{i\in[6],j\in[5]}\{e_{i}^{(j)}\}$, since it satisfies the exact repair property and the data recovery property.

Note that both DSSs in Fig. 11 reliably store $\mathcal{M}=30$ sub-symbols, by using the node capacity of $\alpha=10$ sub-symbols and the repair bandwidth of $\gamma=10$ sub-symbols. However, the former system requires $\gamma_{c}=6$ cross-cluster repair bandwidth for each node failure event, while the latter system requires $\gamma_{c}=0$ cross-cluster repair bandwidth. For example, if the leftmost node of the $1^{st}$ cluster fails in Fig. 11a, then four sub-symbols $\{c_{1}^{(i)},c_{2}^{(i)}\}_{i=1}^{2}$ are transmitted within that cluster, while six sub-symbols $\{c_{3}^{(i)},c_{4}^{(i)},c_{5}^{(i)}\}_{i=1}^{2}$ are transmitted from the $2^{nd}$ cluster. In the case of $\epsilon=0$ in Fig. 11b, ten sub-symbols $\{e_{1}^{(i)},e_{2}^{(i)}\}_{i=1}^{5}$ are transmitted within the $1^{st}$ cluster and no sub-symbols are transmitted across the clusters, when the leftmost node of the $1^{st}$ cluster fails. Thus, transition from the former system (Fig. 11a) to the latter system (Fig. 11b) reduces the cross-cluster repair bandwidth to zero, while maintaining the storage capacity $\mathcal{M}$ and the required resource pair $(\alpha,\gamma)$. Likewise, we can reduce the cross-cluster repair bandwidth to zero while maintaining the storage capacity, in the case of $R=k/n\rightarrow 1$.

Note that $\gamma_{mbr}^{(\epsilon)}=\alpha_{mbr}^{(\epsilon)}$ for $0\leq\epsilon\leq 1$, from (29). Thus, the result of (32) in Theorem 4 can be expressed as Fig. 12 at the asymptotic regime of large $n,k$. According to Fig. 12, intra-cluster only repair ($\epsilon=0$ or $\beta_{c}=0$) is possible by using additional resources ($\alpha$ and $\gamma$) in the $1-R$ portion, compared to the symmetric repair ($\epsilon=1$) case.

Figure 12: Relationship between MBR point of $\epsilon=0$ and that of $\epsilon=1$

IV-C Intra-cluster Repairable Codes versus Locally Repairable Codes [32]

Here, we define a family of network coding schemes for clustered DSS, which we call the intra-cluster repairable codes. In Corollary 1, we considered DSSs with $\epsilon=0$, which can repair any failed node by using intra-cluster communication only. The optimal $(\alpha,\gamma)$ trade-off curve which satisfies $\epsilon=0$ is illustrated as the solid line with cross markers in Fig. 7. Each point on the curve is achievable (i.e., there exists a network coding scheme), according to the result of [11]. We call the network coding schemes for the points on the curve of $\epsilon=0$ the intra-cluster repairable codes, since these coding schemes can repair any failed node by using intra-cluster communication only. The relationship between the intra-cluster repairable codes and the locally repairable codes (LRC) of [32] are investigated in Theorem 5, the proof of which is given in Appendix D. Note that according to the definition in [32], an $(n,l_{0},m_{0},\mathcal{M},\alpha)$-LRC encodes a file of size $\mathcal{M}$ into $n$ coded symbols, where each symbol contains $\alpha$ bits. In addition, any coded symbol of the LRC is regenerated by accessing at most $l_{0}$ other symbols (i.e., the code has repair locality of $l_{0}$), while the minimum distance of the code is $m_{0}$.

Theorem 5.

The intra-cluster repairable codes with storage overhead $\alpha$ are the $(n,l_{0},m_{0},\mathcal{M},\alpha)$-LRC codes of [32] where

$$l_{0} =n_{I}-1,$$

$$m_{0} =n-k+1.$$

It is confirmed that Theorem 1 of [32],

$$m_{0}\leq n-\bigg{\lceil}\frac{\mathcal{M}}{\alpha}\bigg{\rceil}-\bigg{\lceil}\frac{\mathcal{M}}{l_{0}\alpha}\bigg{\rceil}+2,$$ (34)

holds for every intra-cluster repairable code with storage overhead $\alpha$. Moreover, the equality of (34) holds if

$$\alpha=\alpha_{msr}^{(0)},(k\ \mathrm{mod}\ n_{I})\neq 0.$$

IV-D Required $\beta_{c}$ for a given $\alpha$

Here we focus on the following question: when the available intra-cluster repair bandwidth is abundant, how much cross-cluster repair bandwidth is required to reliably store file $\mathcal{M}$? We consider scenarios when the intra-cluster repair bandwidth (per node) has its maximum value, i.e., $\beta_{I}=\alpha$. Under this setting, Theorem 6 specifies the minimum required $\beta_{c}$ which satisfies $\mathcal{C}(\alpha,\beta_{I},\beta_{c})\geq\mathcal{M}$. The proof of Theorem 6 is given in Appendix E.

Theorem 6.

Suppose the intra-cluster repair bandwidth is set at the maximum value, i.e., $\beta_{I}=\alpha$. For a given node capacity $\alpha$, the clustered DSS can reliably store data $\mathcal{M}$ if and only if $\beta_{c}\geq\beta_{c}^{*}$ where

$$\beta_{c}^{*} =\begin{cases}\frac{\mathcal{M}-(k-1)\alpha}{n-k},&\text{ if }\alpha\in[\frac{\mathcal{M}}{k},\frac{\mathcal{M}}{f_{k-1}})\\ \frac{\mathcal{M}-m\alpha}{\sum_{i=m+1}^{k}(n-i)},&\text{ if }\alpha\in[\frac{\mathcal{M}}{f_{m+1}},\frac{\mathcal{M}}{f_{m}})\\ &\quad\quad(m=k-2,k-3,\cdots,s+1)\\ \frac{\mathcal{M}-k_{0}\alpha}{\sum_{i=k_{0}+1}^{k}(n-i)},&\text{ if }\alpha\in[\frac{\mathcal{M}}{f_{k_{0}+1}},\frac{\mathcal{M}}{k_{0}})\\ 0,&\text{ if }\alpha\in[\frac{\mathcal{M}}{k_{0}},\infty),\end{cases}$$ (35)

$$f_{m} =m+\frac{\sum_{i=m+1}^{k}(n-i)}{n-m},$$ (36)

$$k_{0} =k-\lfloor\frac{k}{n_{I}}\rfloor.$$ (37)

Figure 13: Optimal tradeoff between cross-cluster repair bandwidth and node capacity, when $n=100,k=85,L=10,\mathcal{M}=85$ and $\beta_{I}=\alpha$

Fig. 13 provides an example of the optimal trade-off relationship between $\beta_{c}$ and $\alpha$, explained in Theorem 6. For $\alpha\geq\mathcal{M}/k_{0}=1.104$, the cross-cluster burden $\beta_{c}$ can be reduced to zero. However, as $\alpha$ decreases from $\mathcal{M}/k_{0}$, the system requires a larger $\beta_{c}$ value. For example, if $\alpha=\beta_{I}=1.05$ in Fig. 13, $\beta_{c}\geq 0.03$ is required to satisfy $\mathcal{C}(\alpha,\beta_{I},\beta_{c})\geq\mathcal{M}=85$. Thus, for each node failure event, a cross-cluster repair bandwidth of $\gamma_{c}=(n-n_{I})\beta_{c}\geq 2.7$ is required. Theorem 6 provides an explicit equation for the cross-cluster repair bandwidth we need to pay, in order to reduce node capacity $\alpha$.

V Further Comments & Future Works

V-A Explicit coding schemes for clustered DSS

According to the part I proof of Theorem 1, there exists an information flow graph $G^{*}$ which has the min-cut value of $\mathcal{C}$, the capacity of clustered DSS. Thus, according to [11], there exists a linear network coding scheme which achieves capacity $\mathcal{C}$. Although the existence of a coding scheme is verified, explicit network coding schemes which achieve capacity need to be specified for implementing practical systems. Recently, under the setting of clustered DSS modeled in the present paper, MBR codes for all $n,k,L,\epsilon$ are constructed in [36] and MSR codes for limited parameters are designed in [37]. Explicit code construction for general parameters and/or construction of codes that requires small field size are interesting remaining issues.

V-B Optimal number of clusters

According to Theorem 2, capacity $\mathcal{C}$ is asymptotically a monotonically decreasing function of $L$, the number of clusters. Thus, reducing the number of clusters (i.e., gathering storage nodes into a smaller number of clusters) increases storage capacity. However, as mentioned in Section III-E, we typically want to have a sufficiently large $L$, to tolerate the failure of a cluster. Then, the remaining question is in finding optimal $L^{*}$ which not only allows sufficiently large storage capacity, but also a tolerance to cluster failures. We regard this problem as a future research topic, the solution to which will provide a guidance on the strategy for distributing storage nodes into multiple clusters.

V-C Extension to general $d_{I},d_{c}$ settings

The present paper assumed a maximum helper node setting, $d_{I}=n_{I}-1$ and $d_{c}=n-n_{I}$, since it maximizes the capacity as stated in Proposition 1. However, waiting for all helper nodes gives rise to a latency issue. If we reduce the number of helper nodes $d_{I}$ and $d_{c}$, low latency repair would be possible, while the achievable storage capacity decreases. Thus, we consider obtaining the capacity expression for general $d_{I},d_{c}$ settings, and discover the trade-off between capacity and latency for various $d_{I},d_{c}$ values.

V-D Scenarios of aggregating the helper data within each cluster

In recent work [28], [38] on multi-rack (multi-cluster) distributed storage, the authors discuss aggregation of repair data leaving a given cluster. The ideas is to allow aggregation and compression of all helper data leaving each cluster to aid reconstruction taking place in some other cluster containing a failed node. This type of repair link aggregation has been shown to reduce the cross-cluster repair burden in [28], [38]. We expect that the same method would also change the tradeoff picture for our distributed cluster model. This is certainly an interesting and important topic to investigate, but careful analysis including the effect of security breach on links will provide a more complete assessment of the merits and potential perils of repair link aggregation. We will leave this as a future endeavor.

VI Conclusion

This paper considered a practical distributed storage system where storage nodes are dispersed into several clusters. Noticing that the traffic burdens of intra- and cross-cluster communications are typically different, a new system model for clustered distributed storage systems is suggested. Based on the cut-set bound analysis of information flow graph, the storage capacity $\mathcal{C}(\alpha,\beta_{I},\beta_{c})$ of the suggested model is obtained in a closed-form, as a function of three main resources: node storage capacity $\alpha$, intra-cluster repair bandwidth $\beta_{I}$ and cross-cluster repair bandwidth $\beta_{c}$. It is shown that the asymmetric repair ($\beta_{I}>\beta_{c}$) degrades capacity, which is the cost for lifting the cross-cluster repair burden. Moreover, in the asymptotic regime of a large number of storage nodes, capacity is shown to be asymptotically equivalent to a monotonic decreasing function of $L$, the number of clusters. Thus, reducing $L$ (i.e., gathering nodes into less clusters) is beneficial for increasing capacity, although we would typically need to guarantee sufficiently large $L$ to tolerate rack failure events.

Using the capacity expression, we obtained the feasible set of ($\alpha,\beta_{I},\beta_{c}$) triplet which satisfies $\mathcal{C}(\alpha,\beta_{I},\beta_{c})\geq\mathcal{M}$, i.e., it is possible to reliably store file $\mathcal{M}$ by using the resource value set ($\alpha,\beta_{I},\beta_{c}$). The closed-form solution on the feasible set shows a different behavior depending on $\epsilon=\beta_{c}/\beta_{I}$, the ratio of cross- to intra-cluster repair bandwidth. It is shown that the minimum storage of $\alpha=\mathcal{M}/k$ is achievable if and only if $\epsilon\geq\frac{1}{n-k}$. Moreover, in the special case of $\epsilon=0$, we can construct a reliable storage system without using cross-cluster repair bandwidth. A family of network codes which enable $\epsilon=0$, called the intra-cluster repairable codes, has been shown to be a class of the locally repairable codes defined in [32].

Appendix A Proof of Theorem 1

Here, we prove Theorem 1. First, denote the right-hand-side (RHS) of (5) as

$$T\coloneqq\sum_{i=1}^{n_{I}}\sum_{j=1}^{g_{i}}\min\{\alpha,\rho_{i}\beta_{I}+(n-\rho_{i}-j-\sum_{m=1}^{i-1}g_{m})\beta_{c}\}.$$ (A.1)

For other notations used in this proof, refer to subsection II-C. The proof proceeds in two parts.

Part I. Show an information flow graph $G^{*}\in\mathcal{G}$ and a cut-set $c^{*}\in C(G^{*})$ such that $w(G^{*},c^{*})=T$:

Figure 14: The information flow graph $G^{*}$ for the part I proof of Theorem 1

Consider the information flow graph $G^{*}$ illustrated in Fig. 14, which is obtained by the following procedure. First, data from source node $S$ is distributed into $n$ nodes labeled from $x^{1}$ to $x^{n}$. As mentioned in Section II-B, the storage node $x^{i}=(x^{i}_{in},x^{i}_{out})$ consists of an input-node $x_{in}^{i}$ and an output-node $x_{out}^{i}$. Second, storage node $x^{t}$ fails and is regenerated at the newcomer node $x^{n+t}$ for $t\in[k]$. The newcomer node $x^{n+t}$ connects to $n-1$ survived nodes $\{x^{m}\}_{m=t+1}^{n+t-1}$ to regenerate $x^{t}$. Third, data collector node $DC$ contacts $\{x^{n+t}\}_{t=1}^{k}$ to retrieve data. This whole process is illustrated in the information flow graph $G^{*}$.

Figure 15: 2-dim. structure representation

To specify $G^{*}$, here we determine the 2-dimensional location of the $k$ newcomer nodes $\{x^{n+t}\}_{t=1}^{k}$. First, consider the 2-dimensional structure representation of clustered distributed storage, illustrated in Fig. 15. In this figure, each row represents each cluster, and each node is represented as a 2-dimensional $(i,j)$ point for $i\in[L]$ and $j\in[n_{I}]$. The symbol $N(i,j)$ denotes the node at $(i,j)$ point. Here we define the set of $n$ nodes,

$$\mathcal{N}\coloneqq\{N(i,j):i\in[L],j\in[n_{I}]\}.$$ (A.2)

For $t\in[k]$, consider selecting the newcomer node $x^{n+t}$ as

$$x^{n+t}=N(i_{t},j_{t})$$ (A.3)

where

$$i_{t} =\min\{\nu\in[n_{I}]:\sum_{m=1}^{\nu}g_{m}\geq t\},$$ (A.4)

$$j_{t} =t-\sum_{m=1}^{i_{t}-1}g_{m},$$ (A.5)

and $g_{m}$ used in the method is defined in (7). The location of $k$ newcomer nodes selected by this method are illustrated in Fig. 16. Moreover, for the $n=12,L=3,k=9$ case, the newcomer nodes $\{x^{n+t}\}_{t=1}^{k}$ are depicted in Fig. 17. In these figures, the node with number $t$ inside represents the newcomer node labeled as $x^{n+t}$.

Figure 16: The location of $k$ newcomer nodes: $x^{n+1},\cdots,x^{n+k}$

Figure 17: The location of $k$ newcomer nodes for $n=12,L=3,k=9$ case

For the given graph $G^{*}$, now we consider a cut-set $c^{*}\in C(G^{*})$ defined as below. The cut-set $c^{*}=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ can be defined by specifying $U$ and $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$ (complement of $U$), which partition the set of vertices in $G^{*}$. First, let $x^{i}_{in},x^{i}_{out}\in U$ for $i\in[n]$ and $x^{n+i}_{out}\in\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$ for $i\in[k]$. For $i\in[k]$, the input node $x^{n+i}_{in}$ is included in either $U$ or $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$, depending on the condition specified in the next paragraph. Moreover, let $S\in U$ and $DC\in\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$. See Fig. 18.

Let $U_{0}=\bigcup_{i=1}^{n}\{x^{i}_{out}\}$. For $t\in[k]$, let $\omega_{t}^{*}$ be the sum of capacities of edges from $U_{0}$ to $x^{n+t}_{in}$. If $\alpha\leq\omega_{t}^{*}$, then we include $x_{in}^{n+t}$ in $U$. Otherwise, we include $x^{n+t}_{in}$ in $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$. Then, the cut-set $c^{*}$ has the cut-value of

$$w(G^{*},c^{*})=\sum_{t=1}^{k}\min\{\alpha,\omega_{t}^{*}\}.$$ (A.6)

All that remains is to show that (A.6) is equal to the expression in (A.1). In other words, we will obtain the expression for $\omega_{t}^{*}$.

Recall that in the generation process of $G^{*}$, any newcomer node $x^{n+t}$ connects to $n-1$ helper nodes $\{x^{m}\}_{m=t+1}^{n+t-1}$ to regenerate $x^{t}$. Among the $n-1$ helper nodes, the $n_{I}-1$ nodes reside in the same cluster with $x^{t}$, while the $n-n_{I}$ nodes are in other clusters. From our system setting in Section III-A, the helper nodes in the same cluster as the failed node help by $\beta_{I}$, while the helper nodes in other clusters help by $\beta_{c}$. Therefore, the total repair bandwidth to regenerate any failed node is

$$\gamma=(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}$$ (A.7)

as in (2).

The newcomer node $x^{n+1}_{in}$ connects to $\{x_{out}^{m}\}_{m=2}^{n}$, all of which are included in $U_{0}$. Therefore, $\omega_{1}^{*}=\gamma=(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}$ holds. Next, $x^{n+2}_{in}$ connects to $n-2$ nodes $\{x_{out}^{m}\}_{m=3}^{n}$ from $U_{0}$ and one node $x_{out}^{n+1}$ from $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$. Define variable $\beta_{lm}$ as the repair bandwidth from $x_{out}^{n+l}$ to $x_{in}^{n+m}$. Then, $\omega_{2}^{*}=\gamma-\beta_{12}$. From (A.3), we have $x^{n+1}=N(1,1)$ and $x^{n+2}=N(1,2)$. Therefore, $x^{n+1}$ and $x^{n+2}$ are in different clusters, which result in $\beta_{12}=\beta_{c}$. Therefore, $\omega_{2}^{*}=\gamma-\beta_{12}=\gamma-\beta_{c}.$

Figure 18: The cut-set $c^{*}=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ for the graph $G^{*}$

In general, $x^{n+t}_{in}$ connects to $n-t$ nodes $\{x_{out}^{m}\}_{m=t+1}^{n}$ from $U_{0}$, and $t-1$ nodes $\{x_{out}^{n+m}\}_{m=1}^{t-1}$ from $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$. Thus, $\omega_{t}^{*}$ for $t\in[k]$ can be expressed as $\omega_{t}^{*}=\gamma-\sum_{l=1}^{t-1}\beta_{lt}$ where

$$\beta_{lt}=\begin{cases}\beta_{I},&\text{ if }x^{n+l}\text{ and }x^{n+t}\text{ are in the same cluster}\\ \beta_{c},&\text{ otherwise.}\end{cases}$$

Recall Fig. 16. For arbitrary newcomer node $x^{n+t}=N(i_{t},j_{t})$, the set $\{x^{n+m}\}_{m=1}^{t-1}$ contains $i_{t}-1$ nodes which reside in the same cluster with $x^{n+t}$, and $t-i_{t}$ nodes in other clusters. Therefore, $\omega_{t}^{*}$ can be expressed as

$$\omega_{t}^{*}=\gamma-(i_{t}-1)\beta_{I}-(t-i_{t})\beta_{c}$$

where $i_{t}$ is defined in (A.4). Combined with (A.7) and (A.5), we get

$$\omega_{t}^{*} =(n_{I}-i_{t})\beta_{I}+(n-n_{I}-t+i_{t})\beta_{c}$$

$$=(n_{I}-i_{t})\beta_{I}+(n-n_{I}-j_{t}-\sum_{m=1}^{i_{t}-1}g_{m}+i_{t})\beta_{c}.$$

Then, (A.6) can be expressed as

$$w(G^{*},c^{*})=$$

$$\sum_{i=1}^{n_{I}}\sum_{t\in T_{i}}\min\{\alpha,(n_{I}-i)\beta_{I}+(n-n_{I}-j_{t}-\sum_{m=1}^{i-1}g_{m}+i)\beta_{c}\}$$ (A.8)

where $T_{i}=\{t\in[k]:i_{t}=i\}$. From the definition of $i_{t}$ in (A.4), we have

$$T_{i}=\{\sum_{m=1}^{i-1}g_{m}+1,\sum_{m=1}^{i-1}g_{m}+2,\cdots,\sum_{m=1}^{i}g_{m}\}.$$

Thus, $j_{t}=1,2,\cdots,g_{i}$ for $t\in T_{i}$. Therefore, (A) can be expressed as

$$w(G^{*},c^{*})=$$

$$\sum_{i=1}^{n_{I}}\sum_{j=1}^{g_{i}}\min\{\alpha,(n_{I}-i)\beta_{I}+(n-n_{I}-j-\sum_{m=1}^{i-1}g_{m}+i)\beta_{c}\},$$

which is identical to $T$ in (A.1), where $\rho_{i}$ used in this equation is defined in (6). Therefore, the specified information flow graph $G^{*}$ and the specified cut-set $c^{*}$ satisfy $\omega(G^{*},c^{*})=\sum_{t=1}^{k}\min\{\alpha,\omega_{t}^{*}\}=T$.

Part II. Show that for every information flow graph $G\in\mathcal{G}$ and for every cut-set $c\in C(G)$, the cut-value $w(G,c)$ is greater than or equal to $T$ in (A.1). In other words, $\forall G\in\mathcal{G},\forall c\in C(G)$, we have $w(G,c)\geq T$.

The proof is divided into 2 sub-parts: Part II-1 and Part II-2.

Part II-1. Show that $\forall G\in\mathcal{G},\forall c\in C(G),$ we have $w(G,c)\geq B(G,c)$ where $B(G,c)$ is in (A.14):

Consider an arbitrary information flow graph $G\in\mathcal{G}$ and an arbitrary cut-set $c\in C(G)$ of the graph $G$. Denote the cut-set as $c=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$. Consider an output node $x_{out}^{i}$ connected to $DC$. If $x_{out}^{i}\in U$, then the cut-value $w(G,c)$ is infinity, which is a trivial case for proving $w(G,c)\geq B(G,c)$. Therefore, the $k$ output nodes connected to $DC$ are assumed to be in $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$. In other words, at least $k$ output nodes exist in $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$. Note that every directed acyclic graph can be topologically sorted [34], where vertex $u$ is followed by vertex $v$ if there exists a directed edge from $u$ to $v$. Consider labeling the topologically first $k$ output nodes in $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$ as $v_{out}^{1},\cdots,v_{out}^{k}$. Similar to the notation for a storage node $x^{i}=(x^{i}_{in},x^{i}_{out})$ in Section II-B, we denote the storage node which contains $v^{i}_{out}$ as $v^{i}=(v^{i}_{in},v^{i}_{out})$. Then, the set of ordered $k-$tuples $(v^{i})_{i=1}^{k}$ can be represented as

$$\mathcal{V}_{k}=\{(v^{1},v^{2},\cdots,v^{k}): \quad v^{t}\in\mathcal{N}\text{ for }t\in[k]$$

$$\quad v^{t_{1}}\neq v^{t_{2}}\text{ for }t_{1}\neq t_{2}\}.$$ (A.9)

We also define $u_{i}$, the sum of capacities of edges from $U$ to $v_{in}^{i}$. See Fig. 19.

Figure 19: Arbitrary information flow graph $G\in\mathcal{G}$ and arbitrary cut-set $c\in C(G)$

If $v_{in}^{1}\in U$, then the cut-set $c=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ should include the edge from $v_{in}^{1}$ to $v_{out}^{1}$, which has the edge capacity $\alpha$. Otherwise (i.e., $v_{in}^{1}\in\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$), the cut-set $c=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ should include the edges from $U$ to $v_{in}^{1}$. If $v_{in}^{1}$ node is directly connected to the source node $S$, the cut-value $w(G,c)$ is infinity (trivial case for proving $w(G,c)\geq B(G,c)$). Therefore, $v_{in}^{1}$ node is assumed to be a newcomer node helped by $n-1$ helper nodes. Note that all helper nodes of $v_{in}^{1}$ are in $U$, since $v_{out}^{1}$ is the topologically first output node in $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$. Thus, the cut-set $c$ should include the edges from $U$ to $v_{in}^{1}$, where the sum of capacities of these edges are

$$u_{1}=\gamma=(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}.$$

If $v_{in}^{2}\in U$, then the cut-set $c=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ should include the edge from $v_{in}^{2}$ to $v_{out}^{2}$, which has the edge capacity $\alpha$. Otherwise (i.e., $v_{in}^{2}\in\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$), the cut-set $c=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ should include the edges from $U$ to $v_{in}^{2}$. As we discussed in the case of $v_{in}^{1}$, we can assume $v_{in}^{2}$ is a newcomer node helped by $n-1$ helper nodes. Since $v_{in}^{2}$ is the topologically second node in $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$, it may have one helper node $v_{out}^{1}\in\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$; at least $n-2$ helper nodes in $U$ help to generate $v_{in}^{2}$. Note that the total amount of data coming into $v_{in}^{2}$ is $\gamma=(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}$, while the amount of information coming from $v_{out}^{1}$ to $v_{in}^{2}$, denoted $\beta_{12}$, is as follows: if $v^{1}$ and $v^{2}$ are in the same cluster, $\beta_{12}=\beta_{I}$, otherwise $\beta_{12}=\beta_{c}$. Recall that the cut-set should include the edges from $U$ to $v_{in}^{2}$. The sum of capacities of these edges are

$$u_{2}\geq\gamma-\beta_{12},$$

while the equality holds if and only if $v_{out}^{1}$ helps $v_{in}^{2}$. In a similar way, for $i\in[k]$, $u_{i}$ can be bounded as

$$u_{i}\geq\omega_{i}$$ (A.10)

where

$$\omega_{i} =\gamma-\displaystyle\sum_{j=1}^{i-1}\beta_{ji},$$ (A.11)

$$\beta_{ji} =\begin{cases}\beta_{I},&v^{j}\text{ and }v^{i}\text{ are in the same cluster}\\ \beta_{c},&\text{otherwise.}\\ \end{cases}$$ (A.12)

The equality in (A.10) holds if and only if $v_{out}^{j}$ helps $v_{in}^{i}$ for $j\in[i-1]$.

Thus, $v_{out}^{i}$ contributes at least $\min\{\alpha,\omega_{i}\}$ to the cut value, for $i\in[k]$. In summary, for arbitrary graph $G\in\mathcal{G}$, an arbitrary cut-set $c$ has cut-value $w(G,c)$ of at least $\sum_{i=1}^{k}\min\{\alpha,\omega_{i}\}$:

$$w(G,c)\geq\sum_{i=1}^{k}\min\{\alpha,\omega_{i}\},\quad\quad\forall G\in\mathcal{G},\forall c\in C(G).$$ (A.13)

Note that $\{\omega_{i}\}$ depends on the relative position of $\{v_{out}^{i}\}_{i=1}^{k}$, which is determined when an arbitrary information flow graph $G\in\mathcal{G}$ and arbitrary cut-set $c\in C(G)$ are specified. This relationship is illustrated in Fig. 20. Therefore, we define

$$B(G,c)=\sum_{i=1}^{k}\min\{\alpha,\omega_{i}\}$$ (A.14)

for arbitrary $G\in\mathcal{G}$ and arbitrary $c\in C(G)$. Combining (A.13) and (A.14) completes the proof part II-1.

Figure 20: Dependency graph for variables in the proof of Part II.

Part II-2. $\displaystyle\min_{G\in\mathcal{G}}\ \min_{c\in C(G)}B(G,c)=R$:

Assume that $\alpha$ and $k$ are fixed. See Fig. 20. Note that for a given graph $G\in\mathcal{G}$ and a cut-set $c=(U,\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu)$ with $c\in C(G)$, the sequence of topologically first $k$ output nodes $(v_{out}^{i})_{i=1}^{k}$ in $\mkern 1.5mu\overline{\mkern-1.5muU\mkern-1.5mu}\mkern 1.5mu$ is determined. Moreover, for a given sequence $(v_{out}^{i})_{i=1}^{k}$, we have a fixed $(\omega_{i})_{i=1}^{k}$, which determines $B(G,c)$ in (A.14). Thus, $\displaystyle\min_{G\in\mathcal{G}}\ \min_{c\in C(G)}B(G,c)$ can be obtained by finding the optimal $(v_{out}^{i})_{i=1}^{k}$ sequence which minimizes $B(G,c)$. It is identical to finding the optimal $(v^{i})_{i=1}^{k}$, the sequence of $k$ different nodes out of $n$ existing nodes in the system. Therefore, based on (A.14) and (A.11), we have

$$\min_{G\in\mathcal{G}}\ \min_{c\in C(G)}B(G,c)=\displaystyle\min_{(v^{i})_{i=1}^{k}\in\mathcal{V}_{k}}\left(\sum_{i=1}^{k}\min\{\alpha,\gamma-\sum_{j=1}^{i-1}\beta_{ji}\}\right)$$ (A.15)

where

$$\beta_{ji}=\begin{cases}\beta_{I},&v^{j}\text{ and }v^{i}\text{ are in the same cluster}\\ \beta_{c},&\text{otherwise.}\\ \end{cases}$$ (A.16)

holds as defined in (A.12), and $\mathcal{V}_{k}$ is defined in (A). In order to obtain the solution for RHS of (A.15), all we need to do is to find the optimal sequence $(v^{i})_{i=1}^{k}$ of $k$ different nodes, which can be divided into two sub-problems: $i)$ finding the optimal way of selecting $k$ nodes $\{v^{i}\}_{i=1}^{k}$ out of $n$ nodes, and $ii)$ finding the optimal order of selected $k$ nodes. Note that there are $n\choose k$ selection methods and $k!$ ordering methods. Each selection method can be assigned to a selection vector $\bm{s}$ defined in Definition 1, and each ordering method can be assigned to an ordering vector $\bm{\pi}$ defined in Definition 2.

First, we define a selection vector $\bm{s}$ for a given $\{v^{i}\}_{i=1}^{k}$.

Definition 1.

Assume arbitrary $k$ nodes are selected as $\{v^{i}\}_{i=1}^{k}$. Label each cluster by the number of selected nodes in a descending order. In other words, the $1^{st}$ cluster contains a maximum number of selected nodes, and the $L^{th}$ cluster contains a minimum number of selected nodes. Under this setting, define the selection vector $\bm{s}=[s_{1},s_{2},\cdots,s_{L}]$ where $s_{i}$ is the number of selected nodes in the $i^{th}$ cluster.

Figure 21: Obtaining the selection vector for given $k$ output nodes $\{v_{out}^{i}\}_{i=1}^{k}$ ($n=15,k=8,L=3$)

Fig. 21 shows an example of selection vector $\bm{s}$ corresponding to the selected $k$ nodes $\{v^{i}\}_{i=1}^{k}$. From the definition of the selection vector, the set of possible selection vectors can be specified as follows.

$$\mathcal{S}=\big{\{}\bm{s} =[s_{1},\cdots,s_{L}]:0\leq s_{i}\leq n_{I},s_{i+1}\leq s_{i},\sum_{i=1}^{L}s_{i}=k\big{\}}.$$

Note that even though ${n\choose k}$ different selections exist, the $\{\omega_{i}\}$ values in (A.11) are only determined by the corresponding selection vector $\bm{s}$. This is because $\{\omega_{i}\}$ depends only on the relative positions of $\{v^{i}\}_{i=1}^{k}$, whether they are in the same cluster or in different clusters. Therefore, comparing the $\{\omega_{i}\}$ values of all $|\mathcal{S}|$ possible selection vectors $\bm{s}$ is enough; it is not necessary to compare the $\{\omega_{i}\}$ values of ${n\choose k}$ selection methods. Now, we define the ordering vector $\bm{\pi}$ for a given selection vector $\bm{s}$.

Definition 2.

Let the locations of $k$ nodes $\{v^{i}\}_{i=1}^{k}$ be fixed with a corresponding selection vector $\bm{s}=[s_{1},\cdots,s_{L}]$. Then, for arbitrary ordering of the selected $k$ nodes, define the ordering vector $\bm{\pi}=[\pi_{1},\cdots,\pi_{k}]$ where $\pi_{i}$ is the index of the cluster which contains $v^{i}$.

For a given $\bm{s}$, the ordering vector $\bm{\pi}$ corresponding to an arbitrary ordering of $k$ nodes is illustrated in Fig. 22. In this figure (and the following figures in this paper), the number $i$ written inside each node means that the node is $v^{i}$. From the definition, an ordering vector $\bm{\pi}$ has $s_{l}$ components with value $l$, for all $l\in[L]$. The set of possible ordering vectors can be specified as

$$\Pi(\bm{s})=\big{\{}\bm{\pi}=[\pi_{1},\cdots,\pi_{k}]:\sum_{i=1}^{k}\mathds{1}_{\pi_{i}=l}=s_{l},\ \forall l\in[L]\big{\}}$$ (A.17)

Note that for given $k$ selected nodes, there exists $k!$ different ordering methods. However, the $\{\omega_{i}\}$ values in (A.11) are only determined by the corresponding ordering vector $\bm{\pi}\in\Pi(\bm{s})$, by similar reasoning for compressing ${n\choose k}$ selection methods to $|\mathcal{S}|$ selection vectors. Therefore, comparing the $\{\omega_{i}\}$ values of all possible ordering vectors $\bm{\pi}$ is enough; it is not necessary to compare the $\{\omega_{i}\}$ values of all $k!$ ordering methods.

Figure 22: Obtaining the ordering vector for given an arbitrary order of $k$ output nodes ($n=15,k=8,L=3$)

Thus, finding the optimal sequence $(v^{i})_{i=1}^{k}$ is identical to specifying the optimal ($\bm{s,\pi}$) pair, which is obtained as follows. Recall that from the definition of $\bm{\pi}=[\pi_{1},\pi_{2},\cdots,\pi_{k}]$ in Definition 2, $\pi_{i}=\pi_{j}$ holds if and only if $v^{i}$ and $v^{j}$ are in the same cluster. Therefore, $\beta_{ji}$ in (A.16) can be expressed by using $\bm{\pi}$ notation:

$$\beta_{ji}(\bm{\pi})=\begin{cases}\beta_{I}&\text{ if }\pi_{i}=\pi_{j}\\ \beta_{c}&\text{ otherwise}\end{cases}$$ (A.18)

Thus, the $\sum_{j=1}^{i-1}\beta_{ji}$ term in (A.15) can be expressed as

$$\sum_{j=1}^{i-1}\beta_{ji}(\bm{\pi}) =(\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}})\beta_{I}+(i-1-\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}})\beta_{c}.$$ (A.19)

Combining (2), (A.15) and (A.19), we have

$$\min_{G\in\mathcal{G}}\ \min_{c\in C(G)}B(G,c)=\displaystyle\min_{\bm{s}\in S}\ \min_{\bm{\pi}\in\Pi(\bm{s})}L(\bm{s},\bm{\pi})$$

where

$$L(\bm{s},\bm{\pi}) =\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(\bm{\pi})\},$$ (A.20)

$$\omega_{i}(\bm{\pi}) =\gamma-\sum_{j=1}^{i-1}\beta_{ji}(\bm{\pi})=a_{i}(\bm{\pi})\beta_{I}+(n-i-a_{i}(\bm{\pi}))\beta_{c},$$ (A.21)

$$a_{i}(\bm{\pi}) =n_{I}-1-\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}}.$$ (A.22)

Therefore, the rest of the proof in part II-2 shows that

$$\min_{\bm{s}\in S}\ \min_{\bm{\pi}\in\Pi(\bm{s})}L(\bm{s},\bm{\pi})=R$$ (A.23)

holds. We begin by stating a property of $\omega_{i}(\bm{\pi})$ seen in (A.21).

Proposition 3.

Consider a fixed selection vector $\bm{s}$. We claim that $\sum_{i=1}^{k}\omega_{i}(\bm{\pi})$ is constant irrespective of the ordering vector $\bm{\pi}\in\Pi(\bm{s})$.

Proof.

Let $\bm{s}=[s_{1},\cdots,s_{L}]$. For an arbitrary ordering vector $\bm{\pi}\in\Pi(\bm{s})$, let $b_{i}(\bm{\pi})=n-i-a_{i}(\bm{\pi})$ where $a_{i}(\bm{\pi})$ is as given in (A.22). For simplicity, we denote $a_{i}(\bm{\pi})$, $b_{i}(\bm{\pi})$ and $\omega_{i}(\bm{\pi})$ as $a_{i}$, $b_{i}$ and $\omega_{i}$, respectively. Then,

$$\sum_{i=1}^{k}(a_{i}+b_{i})=\sum_{i=1}^{k}(n-i)=\textit{constant (const.)}$$ (A.24)

for fixed $n,k$. Note that

$$\sum_{i=1}^{k}a_{i}=k(n_{I}-1)-\sum_{i=1}^{k}\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}}$$ (A.25)

from (A.22). Also, from the definition of $\Pi(\bm{s})$ in (A.17), an arbitrary ordering vector $\bm{\pi}\in\Pi(\bm{s})$ has $s_{l}$ components with value $l$, for all $l\in[L]$. If we define

$$I_{l}(\bm{\pi})=\{i\in[k]:\pi_{i}=l\},$$ (A.26)

then $|I_{l}(\bm{\pi})|=s_{l}$ holds for $l\in[L]$. Then,

$$\sum_{i\in I_{l}(\bm{\pi})}\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}}=0+1+\cdots+(s_{l}-1)=\sum_{t=0}^{s_{l}-1}t.$$

Therefore,

$$\sum_{i=1}^{k}\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}}=\sum_{l=1}^{L}\sum_{i\in I_{l}(\bm{\pi})}\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}}=\sum_{l=1}^{L}\sum_{t=0}^{s_{l}-1}t=\textit{const.}$$

for fixed $L,\bm{s}$. Combining with (A.25),

$$\sum_{i=1}^{k}a_{i}=k(n_{I}-1)-\sum_{l=1}^{L}\sum_{t=0}^{s_{l}-1}t=\textit{const.}$$ (A.27)

for fixed $n,k,L,\bm{s}$. From (A.24) and (A.27) we get

$$\sum_{i=1}^{k}b_{i}=\textit{const.}$$

Therefore, from (A.21),

$$\sum_{i=1}^{k}\omega_{i}=(\sum_{i=1}^{k}a_{i})\beta_{I}+(\sum_{i=1}^{k}b_{i})\beta_{c}=\textit{const.}$$

for every ordering vector $\bm{\pi}\in\Pi(\bm{s})$, if $n,k,L,\beta_{I},\beta_{c}$ and $\bm{s}$ are fixed. ∎

Now, we define a special ordering vector $\bm{\pi}_{v}$ called vertical ordering vector, which is shown to be the optimal ordering vector $\bm{\pi}$ which minimizes $L(\bm{s},\bm{\pi})$ for an arbitrary selection vector $\bm{s}$.

Definition 3.

For a given selection vector $\bm{s}\in\mathcal{S}$, the corresponding vertical ordering vector $\bm{\pi}_{v}(\bm{s})$, or simply denoted as $\bm{\pi}_{v}$, is defined as the output of Algorithm 1.

The vertical ordering vector $\bm{\pi}_{v}$ is illustrated in Fig. 23, for a given selection vector $\bm{s}$ as an example. For $\bm{s}=[4,3,1]$, Algorithm 1 produces the corresponding vertical ordering vector $\bm{\pi}_{v}=[1,2,3,1,2,1,2,1]$. Note that the order of $k=8$ output nodes is illustrated in Fig. 23, as the numbers inside each node. Although the vertical ordering vector $\bm{\pi}_{v}$ depends on the selection vector $\bm{s}$, we use simplified notation $\bm{\pi}_{v}$ instead of $\bm{\pi}_{v}(\bm{s})$. From Fig. 23, obtaining $\bm{\pi}_{v}$ using Algorithm 1 can be analyzed as follows. Moving from the leftmost column to the rightmost column, the algorithm selects one node per cluster. After selecting all $k$ nodes, $\pi_{i}$ stores the index of the cluster which contains the $i^{th}$ selected node. Now, the following Lemma shows that the vertical ordering vector $\bm{\pi}_{v}$ is optimal in the sense of minimizing $L(\bm{s},\bm{\pi})$ for an arbitrary selection vector $\bm{s}$.

Algorithm 1 Generate vertical ordering $\bm{\pi}_{v}$

  Input: $\bm{s}=[s_{1},\cdots,s_{L}]$

  Output: $\bm{\pi}_{v}=[\pi_{1},\cdots,\pi_{k}]$

  Initialization: $l\leftarrow 1$

  for $i=1$ to $k$ do

     if $s_{l}=0$ then

        $l\leftarrow 1$

     end if

     $\pi_{i}\leftarrow l$       (Store the index of cluster)

     $s_{\pi_{i}}\leftarrow s_{\pi_{i}}-1$    (Update the remaining node info.)

     $l\leftarrow(l\ \mathrm{mod}\ L)+1$    (Go to the next cluster)

  end for

Figure 23: The vertical ordering vector $\bm{\pi}_{v}$ for the given selection vector $\bm{s}=[4,3,1]$ (for $n=15,k=8,L=3$ case)

Lemma 3.

Let $\bm{s}\in\mathcal{S}$ be an arbitrary selection vector. Then, a vertical ordering vector $\bm{\pi}_{v}$ minimizes $L(\bm{s},\bm{\pi})$. In other words, $L(\bm{s},\bm{\pi}_{v})\leq L(\bm{s},\bm{\pi})$ holds for arbitrary $\bm{\pi}\in\Pi(\bm{s})$.

Proof.

In the case of $\beta_{c}=0$, we show that $L(\bm{s},\bm{\pi})$ is constant for every $\bm{\pi}\in\Pi(\bm{s})$. From (A.20),

$$L(\bm{s},\bm{\pi})=\sum_{i=1}^{k}\min\{\alpha,a_{i}(\bm{\pi})\beta_{I}\}$$ (A.28)

holds for $\beta_{c}=0$. Using $I_{l}(\bm{\pi})$ in (A.26), note that $[k]$ can be partitioned into $L$ disjoint subsets as $[k]=\bigcup_{l=1}^{L}I_{l}(\bm{\pi}).$ Therefore, (A.28) can be written as

$$L(\bm{s},\bm{\pi})=\sum_{l=1}^{L}\sum_{i\in I_{l}(\bm{\pi})}\min\{\alpha,a_{i}(\bm{\pi})\beta_{I}\}.$$

Recall that $\bm{\pi}\in\Pi(\bm{s})$ contains $s_{l}$ components with value $l$ for $l\in[L]$. Thus, from (A.22),

$$\bigcup_{i\in I_{l}(\bm{\pi})}\{a_{i}(\bm{\pi})\}=\{n_{I}-1,n_{I}-2,\cdots,n_{I}-s_{l}\}$$

for $l\in[L]$. Therefore, $\sum_{i\in I_{l}(\bm{\pi})}\min\{\alpha,a_{i}(\bm{\pi})\beta_{I}\}$ is constant $\forall\bm{\pi}\in\Pi(\bm{s})$ for arbitrary $l\in[L]$. In conclusion, $L(\bm{s},\bm{\pi})$ in (A.28) is constant irrespective of $\bm{\pi}\in\Pi(\bm{s})$ for $\beta_{c}=0$.

The rest of the proof deals with the $\beta_{c}\neq 0$ case. For a given arbitrary $\bm{s}\in\mathcal{S}$, define two subsets of $\Pi(\bm{s})$ as

$$\Pi_{r}=\{\bm{\pi^{*}}\in\Pi(\bm{s}):\ S_{t}(\bm{\pi})\leq S_{t}(\bm{\pi^{*}}),\forall t\in[k],\ \forall\bm{\pi}\in\Pi(\bm{s})\}$$ (A.29)

$$\Pi_{m}=\{\bm{\pi^{*}}\in\Pi(\bm{s}):L(\bm{s},\bm{\pi})\geq L(\bm{s},\bm{\pi}^{*}),\forall\bm{\pi}\in\Pi(\bm{s})\}$$ (A.30)

where $S_{t}(\bm{\pi})=\sum_{i=1}^{t}w_{i}(\bm{\pi})$ is the running sum of $w_{i}(\bm{\pi})$. Here, we call $\Pi_{r}$ the running sum maximizer and $\Pi_{m}$ the min-cut minimizer. Now the proof proceeds in two steps. The first step proves that the running sum maximizer minimizes min-cut, i.e., $\Pi_{r}\subseteq\Pi_{m}$. The second step proves that the vertical ordering vector is a running sum maximizer, i.e., $\bm{\pi}_{v}\in\Pi_{r}$.

Step 1. Prove $\Pi_{r}\subseteq\Pi_{m}$:

Define two index sets for a given ordering vector $\bm{\pi}$:

$$\Omega_{L}(\bm{\pi}) =\{i\in[k]:w_{i}(\bm{\pi})\geq\alpha\}$$

$$\Omega_{s}(\bm{\pi}) =\{i\in[k]:w_{i}(\bm{\pi})<\alpha\}$$ (A.31)

Now define a set of ordering vectors as

$$\Pi_{p}=\{\bm{\pi}\in\Pi(\bm{s}):i\leq j\ \forall i\in\Omega_{L}(\bm{\pi}),\ \forall j\in\Omega_{s}(\bm{\pi})\}.$$ (A.32)

The rest of the proof is divided into 2 sub-steps.

Step 1-1. Prove $\Pi_{m}\subseteq\Pi_{p}$ and $\Pi_{r}\subseteq\Pi_{p}$ by transposition:

Consider arbitrary $\bm{\pi}=[\pi_{1},\cdots,\pi_{k}]\in\Pi_{p}^{c}$. Use a short-hand notation $\omega_{i}$ to represent $\omega_{i}(\bm{\pi})$ for $i\in[k]$. From (A.32), there exists $i>j$ such that $i\in\Omega_{L}(\bm{\pi})$ and $j\in\Omega_{s}(\bm{\pi})$. Therefore, there exists $t\in[k-1]$ such that $t+1\in\Omega_{L}(\bm{\pi})$ and $t\in\Omega_{s}(\bm{\pi})$ hold. By (A),

$$\omega_{t+1}\geq\alpha>\omega_{t}$$ (A.33)

for some $t\in[k-1]$. Note that from (A.21), $\pi_{t}=\pi_{t+1}$ implies $\omega_{t+1}=\omega_{t}-\beta_{I}<\omega_{t}$. Therefore,

$$\pi_{t}\neq\pi_{t+1}$$ (A.34)

should hold to satisfy (A.33). Define an ordering vector $\bm{\pi^{\prime}}=[\pi^{\prime}_{1},\cdots,\pi^{\prime}_{k}]$ as

$$\begin{cases}\pi^{\prime}_{i}=\pi_{i}&i\neq t,t+1\\ \pi^{\prime}_{t}=\pi_{t+1}\\ \pi^{\prime}_{t+1}=\pi_{t}.\end{cases}$$ (A.35)

Use a short-hand notation $\omega^{\prime}_{i}$ to represent $\omega_{i}(\bm{\pi}^{\prime})$ for $i\in[k]$. Note that $\{\omega^{\prime}_{i}\}$ satisfies

$$\begin{cases}\omega^{\prime}_{i}=\omega_{i}&i\neq t,t+1\\ \omega^{\prime}_{t}=\omega_{t+1}+\beta_{c}\\ \omega^{\prime}_{t+1}=\omega_{t}-\beta_{c}\end{cases}$$ (A.36)

for the following reason. First, use simplified notations $a_{i}$ and $a^{\prime}_{i}$ to mean $a_{i}(\bm{\pi})$ and $a_{i}(\bm{\pi}^{\prime})$, respectively. Then, using (A.22), (A.34) and (A.35), we have

$$a_{t}^{\prime} =n_{I}-1-\sum_{j=1}^{t-1}\mathds{1}_{\pi_{j}^{\prime}=\pi_{t}^{\prime}}=n_{I}-1-\sum_{j=1}^{t-1}\mathds{1}_{\pi_{j}=\pi_{t+1}}$$

$$=n_{I}-1-\sum_{j=1}^{t}\mathds{1}_{\pi_{j}=\pi_{t+1}}=a_{t+1}.$$ (A.37)

Similarly,

$$a_{t+1}^{\prime} =n_{I}-1-\sum_{j=1}^{t}\mathds{1}_{\pi_{j}^{\prime}=\pi_{t+1}^{\prime}}=n_{I}-1-\sum_{j=1}^{t-1}\mathds{1}_{\pi_{j}^{\prime}=\pi_{t+1}^{\prime}}$$

$$=n_{I}-1-\sum_{j=1}^{t-1}\mathds{1}_{\pi_{j}=\pi_{t}}=a_{t}.$$ (A.38)

Therefore, from (A.11), (A) and (A), we have

$$\omega^{\prime}_{t} =a^{\prime}_{t}\beta_{I}+(n-t-a^{\prime}_{t})\beta_{c}$$

$$=a_{t+1}\beta_{i}+(n-t-a_{t+1})\beta_{c}=\omega_{t+1}+\beta_{c}.$$

Similarly, $\omega^{\prime}_{t+1}=\omega_{t}-\beta_{c}$ holds. This proves (A.36). Thus, from (A.33) and (A.36),

$$L(\bm{s},\bm{\pi})=\sum_{i=1}^{k}\min\{\alpha,\omega_{i}\}=\sum_{i\notin\{t,t+1\}}\min\{\alpha,\omega_{i}\}+\omega_{t}+\alpha,$$

$$L(\bm{s},\bm{\pi}^{\prime}) =\sum_{i=1}^{k}\min\{\alpha,\omega_{i}^{\prime}\}$$

$$=\sum_{i\notin\{t,t+1\}}\min\{\alpha,\omega_{i}^{\prime}\}+\alpha+(\omega_{t}-\beta_{c})$$

$$=\sum_{i\notin\{t,t+1\}}\min\{\alpha,\omega_{i}\}+\alpha+(\omega_{t}-\beta_{c}).$$

Therefore, $L(\bm{s},\bm{\pi})>L(\bm{s},\bm{\pi}^{\prime})$ holds for $\beta_{c}>0$. In other words, if $\pi\in\Pi_{p}^{c}$, then $\pi\in\Pi_{m}^{c}$. This proves that $\Pi_{p}^{c}\subseteq\Pi_{m}^{c}$ holds for $\beta_{c}\neq 0$.

Similarly, $\Pi_{p}^{c}\subseteq\Pi_{r}^{c}$ can be proved as follows. For the pre-defined ordering vectors $\bm{\pi}$ and $\bm{\pi^{\prime}}$, we have $S_{t}(\bm{\pi})=\sum_{i=1}^{t-1}\omega_{i}+\omega_{t}$ and $S_{t}(\bm{\pi^{\prime}})=\sum_{i=1}^{t-1}\omega_{i}+\omega_{t+1}+\beta_{c}$. Using (A.33), we have $S_{t}(\bm{\pi})<S_{t}(\bm{\pi^{\prime}})$, so that $\bm{\pi}$ cannot be a running-sum maximizer. Therefore, $\Pi_{p}^{c}\subseteq\Pi_{r}^{c}$ holds.

Step 1-2. Prove that $L(\bm{s,\pi^{*}})\leq L(\bm{s,\pi})$, $\forall\bm{\pi}^{*}\in\Pi_{r},\forall\bm{\pi}\in\Pi_{p}\cap\Pi_{r}^{c}$ :

Consider arbitrary $\bm{\pi}^{*}\in\Pi_{r}$ and $\bm{\pi}\in\Pi_{p}\cap\Pi_{r}^{c}$. For $i\in[k]$, let $\omega_{i}^{*}$ and $\omega_{i}$ be short-hand notations for $\omega_{i}(\bm{\pi}^{*})$ and $\omega_{i}(\bm{\pi})$, respectively. Note that from Proposition 3,

$$\sum_{i=1}^{k}\omega_{i}=\sum_{i=1}^{k}\omega_{i}^{*}.$$ (A.39)

Let

$$t =\max\{i\in[k]:w_{i}\geq\alpha\},$$

$$t^{*} =\max\{i\in[k]:w_{i}^{*}\geq\alpha\}$$ (A.40)

Then, from (A.29),

$$\sum_{i=1}^{t}\omega_{i}\leq\sum_{i=1}^{t}\omega_{i}^{*}.$$ (A.41)

Combining with (A.39), we obtain

$$\sum_{i=t+1}^{k}(\omega_{i}-\omega_{i}^{*})\geq 0.$$ (A.42)

Note that from the result of Step 1-1, both $\bm{\pi}$ and $\bm{\pi}^{*}$ are in $\Pi_{p}$. Therefore, $\omega_{i}\geq\alpha$ for $i\in[t]$. Similarly, $\omega_{i}^{*}\geq\alpha$ for $i\in[t^{*}]$. Therefore, (A.20) can be expressed as

$$L(\bm{s},\bm{\pi}) =\sum_{i=1}^{k}\min\{\alpha,\omega_{i}\}=\sum_{i=1}^{t}\alpha+\sum_{i=t+1}^{k}\omega_{i},$$ (A.43)

$$L(\bm{s},\bm{\pi}^{*}) =\sum_{i=1}^{k}\min\{\alpha,\omega_{i}^{*}\}=\sum_{i=1}^{t^{*}}\alpha+\sum_{i=t^{*}+1}^{k}\omega_{i}^{*}.$$ (A.44)

If $t=t^{*}$, then we have

$$L(\bm{s,\pi})-L(\bm{s,\pi^{*}})=\sum_{i=t+1}^{k}(\omega_{i}-\omega_{i}^{*})\geq 0$$

from (A.42). If $t>t^{*}$, we get

$$L(\bm{s,\pi})-L(\bm{s,\pi^{*}})=\sum_{i=t^{*}+1}^{t}(\alpha-\omega_{i}^{*})+\sum_{i=t+1}^{k}(\omega_{i}-\omega_{i}^{*}).$$

From (A), $\omega_{i}^{*}<\alpha$ holds for $i>t^{*}$. Therefore,

$$L(\bm{s,\pi})-L(\bm{s,\pi^{*}})>\sum_{i=t+1}^{k}(\omega_{i}-\omega_{i}^{*})\geq 0$$

from (A.42). In the case of $t<t^{*}$, define $\Delta=\sum_{i=1}^{t}(\omega_{i}-\alpha)$ and $\Delta^{*}=\sum_{i=1}^{t}(\omega_{i}^{*}-\alpha)$. From (A.43),

$$L(\bm{s,\pi})=\sum_{i=1}^{t}\alpha+\sum_{i=t+1}^{k}\omega_{i}=(\sum_{i=1}^{k}\omega_{i})-\Delta.$$

Similarly, from (A.44),

$$L(\bm{s,\pi^{*}}) =\sum_{i=1}^{k}\omega_{i}^{*}-\sum_{i=1}^{t^{*}}(\omega_{i}^{*}-\alpha)$$

$$=\sum_{i=1}^{k}\omega_{i}^{*}-\Delta^{*}-\sum_{i=t+1}^{t^{*}}(\omega_{i}^{*}-\alpha)\leq\sum_{i=1}^{k}\omega_{i}^{*}-\Delta^{*}$$

where the last inequality is from (A). Combined with (A.39) and (A.41), we obtain

$$L(\bm{s,\pi})-L(\bm{s,\pi^{*}})\geq\Delta^{*}-\Delta\geq 0.$$

In summary, $L(\bm{s,\pi^{*}})\leq L(\bm{s,\pi})$ irrespective of the $t,t^{*}$ values, which completes the proof for Step 1-2. From the results of Step 1-1 and Step 1-2, the relationship between the sets can be depicted as in Fig. 24.

Figure 24: Relationship between sets

Consider $\bm{\pi}_{0}\in\Pi_{r}$ and $\bm{\pi}^{*}\in\Pi_{m}\cap\Pi_{r}^{c}$. Then, $L(\bm{s},\bm{\pi}_{0})\leq L(\bm{s},\bm{\pi}^{*})$ from the result of Step 1-2. Based on the definition of $\Pi_{m}$ in (A.30), we can write $L(\bm{s},\bm{\pi_{0}})\leq L(\bm{s},\bm{\pi})$ for every $\bm{\pi}\in\Pi(\bm{s}).$ In other words, $\pi_{0}\in\Pi_{m}$ holds for arbitrary $\pi_{0}\in\Pi_{r}$. Therefore, $\Pi_{r}\subseteq\Pi_{m}$ holds.

Step 2. Prove $\bm{\pi}_{v}\in\Pi_{r}$:

Figure 25: Set of $s_{1}$ lines where $(i,\omega_{i})$ points can position

For a given selection vector $\bm{s}=[s_{1},\cdots,s_{L}]$, consider an arbitrary ordering vector $\bm{\pi}=[\pi_{1},\cdots,\pi_{k}]\in\Pi(\bm{s})$. The corresponding $\omega_{i}(\bm{\pi})$ defined in (A.21) is written as

$$w_{i}=(n_{I}-j)\beta_{I}+(n-i-n_{I}+j)\beta_{c}$$ (A.45)

where $j=\sum_{t=1}^{i}\mathds{1}_{\pi_{t}=\pi_{i}}$.

Consider a set of lines $\{l_{j}\}_{j=1}^{n_{I}}$, where line $l_{j}$ represents an equation: $w_{i}=(n_{I}-j)\beta_{I}+(n-i-n_{I}+j)\beta_{c}$. Since we assume $\beta_{I}\geq\beta_{c}$, these lines can be illustrated as in Fig. 25. For a given $\bm{\pi}$, consider marking a $(i,\omega_{i})$ point for $i\in[k]$. Note that the $(i,\omega_{i})$ point is on line $l_{j}$ if and only if

$$j=\sum_{t=1}^{i}\mathds{1}_{\pi_{t}=\pi_{i}}$$ (A.46)

where the summation term in (A.46) represents the number of occurrence of $\pi_{i}$ value in $\{\pi_{t}\}_{t=1}^{i}$. For the example in Fig. 23, when $\bm{s}=[4,3,1]$ and $\bm{\pi}=[1,2,3,1,2,1,2,1]\in\Pi(\bm{s})$, line $l_{3}$ contains the point $(i,\omega_{i})=(6,\omega_{6})$ since $3=\sum_{t=1}^{6}\mathds{1}_{\pi_{t}=\pi_{6}}$.

Recall that $I_{l}(\bm{\pi})=\{i\in[k]:\pi_{i}=l\}$, as defined in (A.26), where $|I_{l}(\bm{\pi})|=s_{l}$ holds $\forall l\in[L]$. For $j\in[n_{I}]$, consider $l\in[L]$ with $s_{l}\geq j$. Let $i_{0}$ be the $j^{th}$ smallest element in $I_{l}(\bm{\pi})$. Then, $j=\sum_{t=1}^{i_{0}}\mathds{1}_{\pi_{t}=l}$ and $\pi_{i_{0}}=l$ hold. Thus, the $(i_{0},\omega_{i_{0}})$ point is on line $l_{j}$. Similarly, we can find

$$p_{j}=\sum_{l=1}^{L}\mathds{1}_{s_{l}\geq j}$$ (A.47)

points on line $l_{j}$, irrespective of the ordering vector $\bm{\pi}\in\Pi(\bm{s})$. Note that

$$\sum_{j=1}^{n_{I}}p_{j}=\sum_{l=1}^{L}\sum_{j=1}^{n_{I}}\mathds{1}_{s_{l}\geq j}=\sum_{l=1}^{L}s_{l}=k,$$ (A.48)

which confirms that Fig. 25 contains $k$ points. Moreover,

$$\forall j\in[n_{I}-1],\ p_{j}\geq p_{j+1}$$ (A.49)

holds from the definition in (A.47).

Figure 26: Optimal packing of $k$ points

In order to maximize the running sum $S_{t}(\bm{\pi})=\sum_{i=1}^{t}w_{i}(\bm{\pi})$ for every $t$, the optimal ordering vector packs $p_{1}$ points in the leftmost area ($i=1,\cdots,p_{1}$), pack $p_{2}$ points in the leftmost remaining area ($i=p_{1}+1,\cdots,p_{1}+p_{2}$), and so on. This packing method corresponds to Fig. 26.

Note that from the definition of $p_{j}$ in (A.47) and Fig. 23, vertical ordering $\bm{\pi}_{v}$ in Definition 3 first chooses $p_{1}$ points on line $l_{1}$, then chooses $p_{2}$ points on line $l_{2}$, and so on. Thus, $\bm{\pi}_{v}$ achieves optimal packing in Fig. 26, which maximizes the running sum $S_{t}(\bm{\pi})$. Therefore, vertical ordering is a running sum maximizer, i.e., $\bm{\pi}_{v}\in\Pi_{r}$. Combining Steps 1 and 2, we conclude that $\bm{\pi}_{v}$ minimizes $L(\bm{s},\bm{\pi})$ among $\bm{\pi}\in\Pi(\bm{s})$ for arbitrary $\bm{s}\in S$. ∎

Now, we define a special selection vector called the horizontal selection vector, which is shown to be the optimal selection vector which minimizes $L(\bm{s},\bm{\pi}_{v})$.

Definition 4.

The horizontal selection vector $\bm{s}_{h}=[s_{1},\cdots,s_{L}]\in\mathcal{S}$ is defined as:

$$s_{i}=\begin{cases}n_{I},&i\leq\lfloor\frac{k}{n_{I}}\rfloor\\ (k\ \mathrm{mod}\ n_{I}),&i=\lfloor\frac{k}{n_{I}}\rfloor+1\\ 0&i>\lfloor\frac{k}{n_{I}}\rfloor+1.\end{cases}$$

Figure 27: The optimal selection vector $\bm{s}_{h}$ and the optimal ordering vector $\bm{\pi}_{v}$ (for $n=15,k=8,L=3$ case)

The graphical illustration of the horizontal selection vector is on the left side of Fig. 27, in the case of $n=15,k=8,L=3$. The following Lemma states that the horizontal selection vector minimizes $L(\bm{s},\bm{\pi}_{v})$.

Lemma 4.

Consider applying the vertical ordering vector $\bm{\pi}_{v}$. Then, the horizontal selection vector $\bm{s}_{h}$ minimizes the lower bound $L(\bm{s},\bm{\pi})$ on the min-cut. In other words, $L(\bm{s}_{h},\bm{\pi}_{v})\leq L(\bm{s},\bm{\pi}_{v})\ \forall\bm{s}\in\mathcal{S}$.

Proof.

From the proof of Lemma 3, the optimal ordering vector turns out to be the vertical ordering vector, where the corresponding $\omega_{i}(\bm{\pi}_{v})$ sequence is illustrated in Fig. 26. Depending on the selection vector $\bm{s}=[s_{1},\cdots,s_{L}]$, the number $p_{j}$ of points on each line $l_{j}$ changes.

Consider an arbitrary selection vector $\bm{s}$. Define a point vector $\bm{p(s)}=[p_{1},\cdots,p_{n_{I}}]$ where $p_{j}$ is the number of points on $l_{j}$, as defined in (A.47). Similarly, define $\bm{p(s_{h})}=[p_{1}^{*},\cdots,p_{n_{I}}^{*}]$. Using Definition 4 and (A.47), we have

$$p_{j}^{*}=\begin{cases}\lfloor\frac{k}{n_{I}}\rfloor+1,&\ j\leq(k\ \mathrm{mod}\ n_{I})\\ \lfloor\frac{k}{n_{I}}\rfloor&\ otherwise\end{cases}$$ (A.50)

Now, we prove

$$\forall t\in[n_{I}],\ \sum_{j=1}^{t}p_{j}^{*}\leq\sum_{j=1}^{t}p_{j}.$$ (A.51)

The proof is divided into two steps: base case and inductive step.

Base Case: We wish to prove that $p_{1}^{*}\leq p_{1}$. Suppose $p_{1}^{*}>p_{1}$ (i.e., $p_{1}\leq p_{1}^{*}-1$). Then,

$$\sum_{l=1}^{n_{I}}p_{l}\leq\sum_{l=1}^{n_{I}}p_{1}\leq\sum_{l=1}^{n_{I}}(p_{1}^{*}-1)$$ (A.52)

where the first inequality is from (A.49). Note that if $(k\ \mathrm{mod}\ n_{I})=0$, then

$$\sum_{l=1}^{n_{I}}p_{l}^{*}=\sum_{l=1}^{n_{I}}p_{1}^{*}>\sum_{l=1}^{n_{I}}(p_{1}^{*}-1).$$ (A.53)

Otherwise,

$$\sum_{l=1}^{n_{I}}p_{l}^{*} =\sum_{l=1}^{(k\ \mathrm{mod}\ n_{I})}p_{l}^{*}+\sum_{l=(k\ \mathrm{mod}\ n_{I})+1}^{n_{I}}p_{l}^{*}$$

$$=\sum_{l=1}^{(k\ \mathrm{mod}\ n_{I})}(\lfloor\frac{k}{n_{I}}\rfloor+1)+\sum_{l=(k\ \mathrm{mod}\ n_{I})+1}^{n_{I}}\lfloor\frac{k}{n_{I}}\rfloor$$

$$>\sum_{l=1}^{n_{I}}\lfloor\frac{k}{n_{I}}\rfloor=\sum_{l=1}^{n_{I}}(p_{1}^{*}-1).$$ (A.54)

Therefore, combining (A.52), (A.53) and (A.54) results in $\sum_{l=1}^{n_{I}}p_{l}<\sum_{l=1}^{n_{I}}p_{l}^{*}=k$, which contradicts (A.48). Therefore, $p_{1}^{*}\leq p_{1}$ holds.

Inductive Step: Assume that $\sum_{l=1}^{l_{0}}p_{l}^{*}\leq\sum_{l=1}^{l_{0}}p_{l}$ for arbitrary $l_{o}\in[n_{I}-1]$. Now we prove that $\sum_{l=1}^{l_{0}+1}p_{l}^{*}\leq\sum_{l=1}^{l_{0}+1}p_{l}$ holds. Suppose not. Then,

$$p_{l_{0}+1}^{*}-\Theta-1\geq p_{l_{0}+1}$$ (A.55)

holds where

$$\Theta=\sum_{l=1}^{l_{0}}(p_{l}-p_{l}^{*}).$$ (A.56)

Using (A.49) and (A.55), we have

$$\sum_{l=l_{0}+1}^{n_{I}}p_{l} \leq\sum_{l=l_{0}+1}^{n_{I}}p_{l_{0}+1}\leq\sum_{l=l_{0}+1}^{n_{I}}(p_{l_{0}+1}^{*}-1-\Theta)$$

$$\leq\sum_{l=l_{0}+1}^{n_{I}}(p_{l_{0}+1}^{*}-1)-\Theta$$ (A.57)

where equality holds for the last inequality iff $l_{0}=n_{I}-1$. Using analysis similar to (A.53) and (A.54) for the base case, we can find that $\sum_{l=l_{0}+1}^{n_{I}}(p_{l_{0}+1}^{*}-1)<\sum_{l=l_{0}+1}^{n_{I}}p_{l}^{*}.$ Combining with (A.57), we get

$$\sum_{l=l_{0}+1}^{n_{I}}p_{l}<\sum_{l=l_{0}+1}^{n_{I}}p_{l}^{*}-\Theta.$$ (A.58)

Equations (A.56) and (A.58) imply $\sum_{l=1}^{n_{I}}p_{l}<\sum_{l=1}^{n_{I}}p_{l}^{*}=k,$ which contradicts (A.48). Therefore, (A.51) holds.

Now define

$$f_{i} =\min\{s\in[n_{I}]:\sum_{l=1}^{s}p_{l}\geq i\}$$ (A.59)

$$h_{i} =\min\{s\in[n_{I}]:\sum_{l=1}^{s}p_{l}^{*}\geq i\}$$ (A.60)

for $i\in[k]$. Then,

$$\forall i\in[k],\ h_{i}\geq f_{i}$$ (A.61)

holds directly from (A.51). Note that since $p_{i}^{*}$ in (A.50) is identical to $g_{i}$ in (7), $h_{i}$ can be written as

$$h_{i}=\min\{s\in[n_{I}]:\sum_{l=1}^{s}g_{l}\geq i\}$$ (A.62)

Consider $\bm{\pi}_{v}(\bm{s})$, the vertical ordering vector for a given selection vector $\bm{s}$. Recall that as in Fig. 26, vertical ordering packs the leftmost $p_{1}$ points on line $l_{1}$, packs the next $p_{2}$ points on line $l_{2}$, and so on. Using (A.45), we can write

$$\omega_{i}=\begin{cases}(n_{I}-1)\beta_{I}+(n-i-n_{I}+1)\beta_{c},\quad&\text{if }i\in[p_{1}]\\ (n_{I}-2)\beta_{I}+(n-i-n_{I}+2)\beta_{c},\quad&\text{if }i-p_{1}\in[p_{2}]\\ \quad\quad\vdots\\ 0\cdot\beta_{I}+(n-i)\beta_{c},&\text{if }i-\sum_{t=1}^{n_{I}-1}p_{t}\\ &\quad\quad\in[p_{n_{I}}]\end{cases}$$

Therefore, using (A.59), we further write

$$\omega_{i}(\bm{\pi}_{v}(\bm{s}))=(n_{I}-f_{i})\beta_{I}+(n-i-n_{I}+f_{i})\beta_{c}.$$ (A.63)

Similarly,

$$\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))=(n_{I}-h_{i})\beta_{I}+(n-i-n_{I}+h_{i})\beta_{c}.$$ (A.64)

Combining (A.61), (A.63) and (A.64), we have

$$\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))\leq\omega_{i}(\bm{\pi}_{v}(\bm{s}))\ \forall i=1,\cdots,k,\forall\bm{s}\in\mathcal{S},$$

since we assume $\beta_{I}\geq\beta_{c}$. Therefore, combining with (A.20), we conclude that $L(\bm{s}_{h},\bm{\pi}_{v})\leq L(\bm{s},\bm{\pi}_{v})$ for arbitrary $\bm{s}\in\mathcal{S}$, which completes the proof of Lemma 4. ∎

From Lemmas 3 and 4, we have

$$\forall\bm{s}\in\mathcal{S},\forall\bm{\pi}\in\Pi(\bm{s}),\ L(\bm{s}_{h},\bm{\pi}_{v})\leq L(\bm{s},\bm{\pi}).$$

All that remains is to compute $L(\bm{s}_{h},\bm{\pi}_{v})$ and check that it is identical to (A.1).

From (A.20), $L(\bm{s}_{h},\bm{\pi}_{v})$ can be written as

$$L(\bm{s}_{h},\bm{\pi}_{v})=\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))\}$$ (A.65)

where $\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))$ is defined in (A.64). From $h_{i}$ in (A.62), we have

$$h_{i}=\begin{cases}1,&i\in[g_{1}]\\ 2,&i-g_{1}\in[g_{2}]\\ &\vdots\\ n_{I},&i-\sum_{t=1}^{n_{I}-1}g_{t}\in[g_{n_{I}}]\end{cases}$$ (A.66)

If we define

$$I_{m}^{*}=\{i\in[k]:h_{i}=m\},$$

then $L(\bm{s}_{h},\bm{\pi}_{v})$ in (A.65) can be expressed as

$$L(\bm{s}_{h},\bm{\pi}_{v})=\sum_{i=1}^{k}\min\{\alpha,(n_{I}-h_{i})\beta_{I}+(n-n_{I}-i+h_{i})\beta_{c}\}$$

$$=\sum_{m=1}^{n_{I}}\sum_{i\in I_{m}^{*}}\min\{\alpha,(n_{I}-m)\beta_{I}+(n-n_{I}-i+m)\beta_{c}\}$$

$$=\sum_{m=1}^{n_{I}}\sum_{i\in I_{m}^{*}}\min\{\alpha,\rho_{m}\beta_{I}+(n-\rho_{m}-i)\beta_{c}\}$$ (A.67)

where $\rho_{m}$ is defined in (6).

Using (A.66), we have

$$I_{m}^{*}=\{\sum_{t=1}^{m-1}g_{t}+1,\cdots,\sum_{t=1}^{m-1}g_{t}+g_{m}\}.$$

for $m\in[n_{I}]$. Therefore, $i\in I_{m}^{*}$ can be represented as

$$i=\sum_{t=1}^{m-1}g_{t}+l$$

for $l\in[g_{m}]$. Using this notation, (A) can be written as

$$L(\bm{s}_{h},\bm{\pi}_{v})=\sum_{m=1}^{n_{I}}\sum_{l=1}^{g_{m}}\min\{\alpha,\rho_{m}\beta_{I}+(n-\rho_{m}-s_{m}^{(l)})\beta_{c}\}$$ (A.68)

where $s_{m}^{(l)}=\sum_{t=1}^{m-1}g_{t}+l$. This expression reduces to (A.1). This completes the proof of Part II-2. Therefore, the storage capacity of clustered DSS is as stated in Theorem 1.

Appendix B Proof of Theorem 3

We begin with introducing properties of the parameters $z_{t}$ and $h_{t}$ defined in (25) and (26).

Proposition 4.

$$h_{k} =n_{I},$$ (B.1)

$$z_{k} =(n-k)\epsilon.$$ (B.2)

Proof.

Since we consider $k>n_{I}$ case as stated in (3), we have

$$g_{i}\geq 1\quad\forall i\in[n_{I}]$$

for $\{g_{i}\}_{i=1}^{n_{I}}$ defined in (7). Combining with (9) and (26), we can conclude that $h_{k}=n_{I}$. Finally, $z_{k}=(n-k)\epsilon$ is from (25) and (B.1). ∎

First, consider the $\epsilon\geq\frac{1}{n-k}$ case. From (20), data $\mathcal{M}$ can be reliably stored with node storage $\alpha=\mathcal{M}/k$ if the repair bandwidth satisfies $\gamma\geq\gamma^{*}$, where

$$\gamma^{*} =\frac{\mathcal{M}-(k-1)\mathcal{M}/k}{s_{k-1}}=\frac{\mathcal{M}}{k}\frac{1}{s_{k-1}}$$

$$=\frac{\mathcal{M}}{k}\frac{(n-k)\epsilon}{(n_{I}-1)+(n-n_{I})\epsilon}$$

where the last equality is from (23) and (B.2). Thus, $\alpha=\mathcal{M}/k$ is achievable with finite $\gamma$, when $\epsilon\geq\frac{1}{n-k}$.

Second, we prove that it is impossible to achieve $\alpha=\mathcal{M}/k$ for $0\leq\epsilon<\frac{1}{n-k}$, in order to reliably store file $\mathcal{M}$. Recall that the minimum storage for $0\leq\epsilon<\frac{1}{n-k}$ is

$$\alpha=\frac{M}{\tau+\sum_{i=\tau+1}^{k}z_{i}}$$ (B.3)

from (28). From (22) and (B.2), we have $z_{i}<1$ for $i=\tau+1,\tau+2,\cdots,k$. Therefore,

$$\tau+\sum_{i=\tau+1}^{k}z_{i}<\tau+(k-(\tau+1)+1)=k$$

holds, which result in

$$\frac{M}{\tau+\sum_{i=\tau+1}^{k}z_{i}}>\frac{\mathcal{M}}{k}.$$ (B.4)

Thus, the $0\leq\epsilon\leq\frac{1}{n-k}$ case has the minimum storage $\alpha$ greater than $\mathcal{M}/k$, which completes the proof of Theorem 3.

Appendix C Proof of Theorem 4

First, we prove (30). To begin with, we obtain the expression of $\alpha_{msr}^{(\epsilon)}$, for $\epsilon=0,1$. From (28), we obtain

$$\alpha_{msr}^{(0)} =\frac{\mathcal{M}}{\tau+\sum_{i=\tau+1}^{k}z_{i}},$$ (C.1)

$$\alpha_{msr}^{(1)} =\frac{\mathcal{M}}{k}.$$

We further simplify the expression for $\alpha_{msr}^{(0)}$ as follows. Recall

$$z_{t}=n_{I}-h_{t}$$ (C.2)

for $t\in[k]$ from (25), when $\epsilon=0$ holds. Note that we have

$$z_{t}=\begin{cases}0,&t\geq k-\lfloor\frac{k}{n_{I}}\rfloor+1\\ 1,&t=k-\lfloor\frac{k}{n_{I}}\rfloor\end{cases}$$ (C.3)

from the following reason. First, from (26) and (C.2), $z_{t}=0$ holds for

$$t \geq\sum_{l=1}^{n_{I}-1}g_{l}+1=\sum_{l=1}^{n_{I}}g_{l}-g_{n_{I}}+1=k-\lfloor\frac{k}{n_{I}}\rfloor+1$$

where the last equality is from (9) and (7). Similarly, we can prove that $z_{t}=1$ holds for $t=k-\lfloor\frac{k}{n_{I}}\rfloor$. From (C.3) and (22), we obtain

$$\tau=k-\lfloor\frac{k}{n_{I}}\rfloor$$ (C.4)

when $\epsilon=0$. Combining (C.1), (C.3) and (C.4), we have

$$\alpha_{msr}^{(0)}=\frac{\mathcal{M}}{k-\lfloor\frac{k}{n_{I}}\rfloor}.$$ (C.5)

Then, using $R=k/n$ and $\sigma=L^{2}/n$,

$$\frac{\alpha_{msr}^{(0)}}{\alpha_{msr}^{(1)}} =\frac{k}{k-\lfloor\frac{k}{n_{I}}\rfloor}=\frac{nR}{nR-\lfloor RL\rfloor}$$

$$=\frac{nR}{nR-\lfloor R\sqrt{n\sigma}\rfloor}=\frac{R}{R-\lfloor R\sqrt{n\sigma}\rfloor/n}.$$

Thus, for arbitrary fixed $R$ and $\sigma$,

$$\lim\limits_{n\rightarrow\infty}\frac{\alpha_{msr}^{(0)}}{\alpha_{msr}^{(1)}}=1.$$

Therefore, $\alpha_{msr}^{(0)}$ is asymptotically equivalent to $\alpha_{msr}^{(1)}$.

Second, we prove (31). Note that from (29), $\alpha_{mbr}^{(\epsilon)}=\gamma_{mbr}^{(\epsilon)}$ holds for arbitrary $0\leq\epsilon\leq 1$. Therefore, all we need to prove is

$$\gamma_{mbr}^{(0)}\rightarrow\gamma_{mbr}^{(1)}.$$

To begin with, we obtain the expression for $\gamma_{mbr}^{(\epsilon)}$, when $\epsilon=0,1$. For $\epsilon=1$, $z_{t}$ in (25) is

$$z_{t}=n-t$$ (C.6)

for $t\in[k]$. Moreover, from (23),

$$s_{0}=\frac{\sum_{i=1}^{k}z_{i}}{n-1}$$ (C.7)

for $\epsilon=1$. Therefore, from (29), (C.6) and (C.7),

$$\gamma_{mbr}^{(1)}=\frac{\mathcal{M}}{s_{0}} =\frac{(n-1)\mathcal{M}}{\sum_{i=1}^{k}(n-i)}=\frac{\mathcal{M}}{k}\frac{2(n-1)}{2n-k-1}.$$ (C.8)

Now we focus on the case of $\epsilon=0$. First, let $q$ and $r$ be

$$q \coloneqq\lfloor\frac{k}{n_{I}}\rfloor,$$ (C.9)

$$r \coloneqq(k\ \mathrm{mod}\ n_{I}),$$ (C.10)

which represent the quotient and remainder of $k/n_{I}$. Note that

$$qn_{I}+r=k.$$ (C.11)

Then, we have

$$\sum_{t=1}^{n_{I}}tg_{t} =\sum_{t=1}^{r}(q+1)t+\sum_{t=r+1}^{n_{I}}qt=q\sum_{t=1}^{n_{I}}t+\sum_{t=1}^{r}t$$

$$=q\frac{n_{I}(n_{I}+1)}{2}+\frac{r(r+1)}{2}=\frac{1}{2}(qn_{I}^{2}+r^{2}+k)$$ (C.12)

where the last equality is from (C.11). From (C.2) and (A.66), we have

$$\sum_{i=1}^{k}z_{i} =\sum_{t=1}^{n_{I}}(n_{I}-t)g_{t}=n_{I}k-\frac{1}{2}(qn_{I}^{2}+r^{2}+k)$$

$$=(n_{I}-1)k-\frac{1}{2}(qn_{I}^{2}+r^{2}-k)$$ (C.13)

where the second last equality is from (9) and (C). Moreover, using (C.11), we have

$$qn_{I}^{2}+r^{2}-k =qn_{I}^{2}+r^{2}-qn_{I}-r$$

$$=(qn_{I}+r)(n_{I}-1)-r(n_{I}-r)$$

$$\leq(qn_{I}+r)(n_{I}-1)=k(n_{I}-1)$$ (C.14)

where the equality holds if and only if $r=0$. Furthermore,

$$s_{0}=\frac{\sum_{i=1}^{k}z_{i}}{n_{I}-1}$$ (C.15)

for $\epsilon=0$ from (23). Combining (29), (C), (C) and (C.15) result in

$$\gamma_{mbr}^{(0)}=\frac{\mathcal{M}}{s_{0}} \leq\frac{2\mathcal{M}}{k}.$$ (C.16)

From (C.8) and (C.16), we have

$$\gamma_{mbr}^{(0)}-\gamma_{mbr}^{(1)} \leq\frac{\mathcal{M}}{k}\left(2-\frac{2(n-1)}{2n-k-1}\right)=\frac{\mathcal{M}}{k}\frac{2(n-k)}{2n-k-1}$$

$$=\frac{\mathcal{M}}{nR}\frac{2n(1-R)}{n(2-R)-1}$$

where $R=k/n$. Thus, for arbitrary $n$,

$$\gamma_{mbr}^{(0)}\rightarrow\gamma_{mbr}^{(1)}$$

as $R\rightarrow 1$. This completes the proof of (31). Finally, (C.8) and (C.16) provides

$$\frac{\gamma_{mbr}^{(0)}}{\gamma_{mbr}^{(1)}} \leq\frac{2n-k-1}{n-1}=2-\frac{k-1}{n-1},$$

which completes the proof of (32).

Appendix D Proof of Theorem 5

Recall the definition of an $(n,l_{0},m_{0},\mathcal{M},\alpha)$-LRC which appear right before Theorem 5. Moreover, recall that the repair locality of a code is defined as the number of nodes to be contacted in the node repair process [32]. Since each cluster contains $n_{I}$ nodes, every node in a DSS with $\epsilon=0$ has the repair locality of

$$l_{0}=n_{I}-1.$$ (D.1)

Moreover, note that for any code with minimum distance $m$, the original file $\mathcal{M}$ can be retrieved by contacting $n-m+1$ coded symbols [38]. Since the present paper considers DSSs such that contacting any $k$ nodes can retrieve the original file $\mathcal{M}$, we have the minimum distance of

$$m_{0}=n-k+1.$$ (D.2)

Thus, the intra-cluster repairable code defined in Section IV-C is a $(n,l_{0},m_{0},\mathcal{M},\alpha)$-LRC.

Now we show that (34) holds. Note that from Fig. 10, we obtain $\alpha\geq\alpha_{msr}^{(0)}$ for $\epsilon=0$, where

$$\alpha_{msr}^{(0)}=\frac{\mathcal{M}}{k-\lfloor\frac{k}{n_{I}}\rfloor}$$ (D.3)

holds according to (C.1). Thus, (34) is proven by showing

$$m_{0}\leq n-\bigg{\lceil}\frac{\mathcal{M}}{\alpha_{msr}^{(0)}}\bigg{\rceil}-\bigg{\lceil}\frac{\mathcal{M}}{l_{0}\alpha_{msr}^{(0)}}\bigg{\rceil}+2.$$ (D.4)

By plugging (D.1), (D.2) and (D.3) into (D.4), we have

$$n-k+1 \leq n-\bigg{\lceil}k-\bigg{\lfloor}\frac{k}{n_{I}}\bigg{\rfloor}\bigg{\rceil}-\bigg{\lceil}\frac{k-\lfloor\frac{k}{n_{I}}\rfloor}{n_{I}-1}\bigg{\rceil}+2$$

$$=n-k+\bigg{\lfloor}\frac{k}{n_{I}}\bigg{\rfloor}-\bigg{\lceil}\frac{k-\lfloor\frac{k}{n_{I}}\rfloor}{n_{I}-1}\bigg{\rceil}+2.$$

Therefore, all we need to prove is

$$0\leq\bigg{\lfloor}\frac{k}{n_{I}}\bigg{\rfloor}-\bigg{\lceil}\frac{k-\lfloor\frac{k}{n_{I}}\rfloor}{n_{I}-1}\bigg{\rceil}+1,$$ (D.5)

which is proved as follows. Using $q$ and $r$ defined in (C.9) and (C.10), the right-hand-side (RHS) of (D.5) is

$$RHS =q-\bigg{\lceil}\frac{qn_{I}+r-q}{n_{I}-1}\bigg{\rceil}+1$$

$$=\begin{cases}q-(q+1)+1=0,&\quad r\neq 0\\ q-q+1=1,&\quad r=0\\ \end{cases}$$

Thus, (D.5) holds, where the equality condition is $r\neq 0$, or equivalently $(k\ \mathrm{mod}\ n_{I})\neq 0$. Therefore, (34) holds, where the equality condition is $\alpha=\alpha_{msr}^{(0)}$ and $(k\ \mathrm{mod}\ n_{I})\neq 0$. This completes the proof of Theorem 5.

Appendix E Proof of Theorem 6

According to (A.20) and (A.68) in Appendix B, the capacity can be expressed as

$$\mathcal{C}=\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))\}.$$ (E.1)

Using (A.64) and (A.66), $\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))$ in (E.1), or simply $\omega_{i}$ has the following property:

$$\omega_{i+1}=\begin{cases}\omega_{i}-\beta_{I},&i\in I_{G}\\ \omega_{i}-\beta_{c},&i\in[k]\setminus I_{G}\end{cases}$$ (E.2)

where $I_{G}=\{g_{m}\}_{m=1}^{n_{I}-1}.$ Note that $g_{n_{I}}=\lfloor\frac{k}{n_{I}}\rfloor$ from (7). Therefore, $k_{0}$ in (37) can be expressed as

$$k_{0}=k-\lfloor\frac{k}{n_{I}}\rfloor=k-g_{n_{I}}\leq k-1$$ (E.3)

where the last inequality is from (3). Combining (26) and (E.3) result in

$$h_{k_{0}}=n_{I}-1.$$ (E.4)

From (A.64), (E.3) and (E.4), we have

$$\omega_{k_{0}} =(n_{I}-h_{k_{0}})\beta_{I}+(n-k_{0}-n_{I}+h_{k_{0}})\beta_{c}$$

$$=\beta_{I}+(n-k_{0}-1)\beta_{c}\geq\beta_{I}+(n-k)\beta_{c}\geq\beta_{I}=\alpha.$$ (E.5)

where the last equality holds due to the assumption of $\beta_{I}=\alpha$ in the setting of Theorem 6. Since $(\omega_{i})_{i=1}^{k}$ is a decreasing sequence from (E.2), the result of (E) implies that

$$\omega_{i}\geq\alpha,\quad\quad 1\leq i\leq k_{0}.$$ (E.6)

Thus, the capacity expression in (E.1) can be expressed as

$$\mathcal{C} =\begin{cases}k_{0}\alpha+\sum_{i=k_{0}+1}^{k}\omega_{i},&\omega_{k_{0}+1}\leq\alpha\\ m\alpha+\sum_{i=m+1}^{k}\omega_{i},&\omega_{m+1}\leq\alpha<\omega_{m}\\ &\ \ \ (k_{0}+1\leq m\leq k-1)\\ k\alpha,&\alpha<\omega_{k}\end{cases}$$ (E.7)

Note that from (A.64) and (A.66), we have $\omega_{i}=(n-i)\beta_{c}$ for $i=k_{0}+1,k_{0}+2,\cdots,k$. Therefore, $\mathcal{C}$ in (E.7) is

$$\mathcal{C} =\begin{cases}k_{0}\alpha+\sum_{i=k_{0}+1}^{k}(n-i)\beta_{c},&0\leq\beta_{c}\leq\frac{\alpha}{n-k_{0}-1}\\ m\alpha+\sum_{i=m+1}^{k}(n-i)\beta_{c},&\frac{\alpha}{n-m}<\beta_{c}\leq\frac{\alpha}{n-m-1}\\ &\ \ \ (k_{0}+1\leq m\leq k-1)\\ k\alpha,&\frac{\alpha}{n-k}<\beta_{c},\end{cases}$$ (E.8)

which is illustrated as a piecewise linear function of $\beta_{c}$ in Fig. 28. Based on (E.8), the sequence $(T_{m})_{m=k_{0}}^{k}$ in this figure has the following expression:

$$T_{m}=\begin{cases}k_{0}\alpha,&m=k_{0}\\ (m+\frac{\sum_{i=m+1}^{k}(n-i)}{n-m})\alpha,&k_{0}+1\leq m\leq k-1\\ k\alpha,&m=k\end{cases}$$ (E.9)

Figure 28: Capacity as a function of $\beta_{c}$

From Fig. 28, we can conclude that $\mathcal{C}\geq\mathcal{M}$ holds if and only if $\beta_{c}\geq\beta_{c}^{*}$ where

$$\beta_{c}^{*}=\begin{cases}0,&\mathcal{M}\in[0,T_{k_{0}}]\\ \frac{\mathcal{M}-m\alpha}{\sum_{i=m+1}^{k}(n-i)},&\mathcal{M}\in(T_{m},T_{m+1}]\\ &\quad(m=k_{0},k_{0}+1,\cdots,k-1)\\ \infty,&\mathcal{M}\in(T_{k},\infty).\end{cases}$$ (E.10)

Using $T_{m}$ in (E.9) and $f_{m}$ in (36), (E.10) reduces to (35), which completes the proof.

Appendix F Proofs of Corollaries

F-A Proof of Corollary 1

From the proof of Theorem 1, the capacity expression is equal to (A), which is

$$\mathcal{C}=\sum_{i=1}^{k}\min\{\alpha,(n_{I}-h_{i})\beta_{I}+(n-n_{I}-i+h_{i})\beta_{c}\}.$$

where $h_{i}$ is defined in (A.60). Using $\epsilon=\beta_{c}/\beta_{I}$ and (2), this can be rewritten as

$$\mathcal{C}=\sum_{i=1}^{k}\min\{\alpha,\frac{(n-n_{I}-i+h_{i})\epsilon+(n_{I}-h_{i})}{(n-n_{I})\epsilon+(n_{I}-1)}\gamma\}.$$ (F.1)

Using $\{z_{t}\}$ and $\{y_{t}\}$ defined in (25) and (24), the capacity expression reduces to

$$\mathcal{C}(\alpha,\gamma)=\sum_{t=1}^{k}\min\{\alpha,\frac{\gamma}{y_{t}}\},$$ (F.2)

which is a continuous function of $\gamma$.

Remark 1.

$\{z_{t}\}$ in (25) is a decreasing sequence of $t$. Moreover, $\{y_{t}\}$ in (24) is an increasing sequence.

Proof.

Note that from (A.62),

$$h_{t+1}=\begin{cases}h_{t}+1,&t\in T\\ h_{t},&t\in[k-1]\setminus T\end{cases}$$

where $T=\{g_{1},g_{1}+g_{2},\cdots,\sum_{m=1}^{n_{I}-1}g_{m}\}.$ Therefore, $\{z_{t}\}$ in (25) is a decreasing function of $t$, which implies that $\{y_{t}\}$ is an increasing sequence. ∎

Moreover, note that $\beta_{I}\leq\alpha$ holds from the definition of $\beta_{I}$ and $\alpha$ in Table I. Thus, combined with $\epsilon=\beta_{I}/\beta_{c}$, it is shown that $\gamma$ in (2) is lower-bounded as

$$\gamma =(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}$$

$$=\{n_{I}-1+(n-n_{I})\epsilon\}\beta_{I}\leq\{n_{I}-1+(n-n_{I})\epsilon\}\alpha.$$

Here, we define

$$\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\mkern 1.5mu=\{n_{I}-1+(n-n_{I})\epsilon\}\alpha.$$

Then, the valid region of $\gamma$ is expressed as $\gamma\leq\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\mkern 1.5mu,$ as illustrated in Figs. 29 and 30. The rest of the proof depends on the range of $\epsilon$ values; we first consider the $\frac{1}{n-k}\leq\epsilon\leq 1$ case, and then consider the $0\leq\epsilon<\frac{1}{n-k}$ case.

F-A1 If $\frac{1}{n-k}\leq\epsilon\leq 1$

Using (B.2), $z_{k}=(n-k)\epsilon\geq 1$ holds. Combining with (24), we have $y_{k}\leq n_{I}-1+\epsilon(n-n_{I}),$ or equivalently, $y_{k}\alpha\leq\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\mkern 1.5mu.$ If $y_{t}\alpha<\gamma\leq y_{t+1}\alpha$ for some $t\in[k-1]$, then (F.2) can be expressed as

$$\mathcal{C}(\alpha,\gamma) =t\alpha+\sum_{m=t+1}^{k}\frac{\gamma}{y_{m}}$$

$$=t\alpha+\frac{\gamma\ (\sum_{m=t+1}^{k}z_{m})}{(n_{I}-1)+\epsilon(n-n_{I})}=t\alpha+s_{t}\gamma$$

where $\{s_{t}\}$ is defined in (23). If $0\leq\gamma\leq y_{1}\alpha$, then

$$\mathcal{C}(\alpha,\gamma) =\sum_{m=1}^{k}\frac{\gamma}{y_{m}}=\frac{\gamma\ (\sum_{m=1}^{k}z_{m})}{(n_{I}-1)+\epsilon(n-n_{I})}=s_{0}\gamma.$$

If $y_{k}\alpha<\gamma\leq\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\mkern 1.5mu$, then $\mathcal{C}(\alpha,\gamma)=\sum_{m=1}^{k}\alpha=k\alpha.$ In summary, capacity is

$$\mathcal{C}(\alpha,\gamma) =\begin{cases}s_{0}\gamma,&0\leq\gamma\leq y_{1}\alpha\\ t\alpha+s_{t}\gamma,&y_{t}\alpha<\gamma\leq y_{t+1}\alpha\\ &\ \ \ \ (t=1,2,\cdots,k-1)\\ k\alpha,&y_{k}\alpha<\gamma\leq\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\end{cases}$$ (F.3)

which is illustrated in Fig. 29. Since $\{z_{t}\}$ is a decreasing sequence from Remark 1, we have $z_{t}\geq z_{k}=(n-k)\epsilon>0$ for $t\in[k]$. Thus, $\{s_{t}\}_{t=1}^{k}$ defined in (23) is a monotonically decreasing, non-negative sequence. This implies that the curve in Fig. 29 is a monotonic increasing function of $\gamma$.

Figure 29: Capacity as a function of $\gamma$, for $\frac{1}{n-k}\leq\epsilon\leq 1$

From Fig. 29, it is shown that $\mathcal{C}(\alpha,\gamma)\geq\mathcal{M}$ holds if and only if $\gamma\geq\gamma^{*}(\alpha)$. From (F.3), the threshold value $\gamma^{*}(\alpha)$ can be expressed as

$$\gamma^{*}(\alpha)=\begin{cases}\frac{\mathcal{M}}{s_{0}},&\mathcal{M}\in[0,E_{1}]\\ \frac{\mathcal{M}-t\alpha}{s_{t}},&\mathcal{M}\in(E_{t},E_{t+1}]\\ &\ \ \ \ (t=1,2,\cdots,k-1)\\ \infty,&\mathcal{M}\in(E_{k},\infty).\end{cases}$$ (F.4)

where

$$E_{t}=\mathcal{C}(\alpha,y_{t}\alpha)=(t-1+s_{t-1}y_{t})\alpha$$ (F.5)

for $t\in[k]$. The threshold value $\gamma^{*}(\alpha)$ in (F.4) can be expressed as (20), which completes the proof.

F-A2 Otherwise (if $0\leq\epsilon<\frac{1}{n-k}$)

Using (B.2),

$$z_{k}=(n-k)\epsilon<1$$ (F.6)

holds. Since $\{z_{t}\}$ is a decreasing sequence from Remark 1, there exists $\tau\in\{0,1,\cdots,k-1\}$ such that $z_{\tau+1}<1\leq z_{\tau}$ holds, or equivalently, $y_{\tau}\alpha\leq\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\mkern 1.5mu<y_{\tau+1}\alpha.$

Using the analysis similar to the $\frac{1}{n-k}\leq\epsilon\leq 1$ case, we obtain

$$\mathcal{C}(\alpha,\gamma) =\begin{cases}s_{0}\gamma,&0\leq\gamma\leq y_{1}\alpha\\ t\alpha+s_{t}\gamma,&y_{t}\alpha<\gamma\leq y_{t+1}\alpha\\ &\ \ \ \ (t=1,2,\cdots,\tau-1)\\ \tau\alpha+s_{\tau}\gamma,&y_{\tau}\alpha<\gamma\leq\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\end{cases}$$ (F.7)

which is illustrated in Fig. 30.

Figure 30: Capacity as a function of $\gamma$, for $0\leq\epsilon<\frac{1}{n-k}$ case

From Fig. 30, it is shown that $\mathcal{C}(\alpha,\gamma)\geq\mathcal{M}$ holds if and only if $\gamma\geq\gamma^{*}(\alpha)$. From (F.7), the threshold value $\gamma^{*}(\alpha)$ can be expressed as

$$\gamma^{*}(\alpha)=\begin{cases}\frac{\mathcal{M}}{s_{0}},&\mathcal{M}\in[0,E_{1}]\\ \frac{\mathcal{M}-t\alpha}{s_{t}},&\mathcal{M}\in(E_{t},E_{t+1}]\\ &\ \ \ \ (t=1,2,\cdots,\tau-1)\\ \frac{\mathcal{M}-\tau\alpha}{s_{\tau}},&\mathcal{M}\in(E_{\tau},\mkern 1.5mu\overline{\mkern-1.5muE\mkern-1.5mu}\mkern 1.5mu]\\ \infty,&\mathcal{M}\in(\mkern 1.5mu\overline{\mkern-1.5muE\mkern-1.5mu}\mkern 1.5mu,\infty).\end{cases}$$ (F.8)

where $\{E_{t}\}$ is defined in (F.5), and

$$\mkern 1.5mu\overline{\mkern-1.5muE\mkern-1.5mu}\mkern 1.5mu=\mathcal{C}(\alpha,\mkern 1.5mu\overline{\mkern-1.5mu\gamma\mkern-1.5mu}\mkern 1.5mu)=\tau\alpha+s_{\tau}\alpha\{n_{I}-1+(n-n_{I})\epsilon\}.$$

The threshold value $\gamma^{*}(\alpha)$ in (F.8) can be expressed as (21), which completes the proof.

F-B Proof of Corollary 2

First, we focus on the MSR point illustrated in Fig. 9. From (20), the MSR point for $\frac{1}{n-k}\leq\epsilon\leq 1$ is

$$(\alpha_{msr}^{(\epsilon)},\gamma_{msr}^{(\epsilon)}) =(\frac{\mathcal{M}}{k+s_{k}y_{k}},\frac{\mathcal{M}-(k-1)\alpha_{msr}^{(\epsilon)}}{s_{k-1}})$$

$$=(\frac{\mathcal{M}}{k},\frac{\mathcal{M}}{k}\frac{1}{s_{k-1}})$$ (F.9)

where the last equality is from $s_{k}=0$ in (23). Moreover, from (21), the MSR point for $0\leq\epsilon<\frac{1}{n-k}$ is

$$(\alpha_{msr}^{(\epsilon)},\gamma_{msr}^{(\epsilon)}) =(\frac{M}{\tau+\sum_{i=\tau+1}^{k}z_{i}},\frac{\mathcal{M}-\tau\alpha_{msr}^{(\epsilon)}}{s_{\tau}})$$

$$=(\frac{M}{\tau+\sum_{i=\tau+1}^{k}z_{i}},\frac{M}{\tau+\sum_{i=\tau+1}^{k}z_{i}}\frac{\sum_{i=\tau+1}^{k}z_{i}}{s_{\tau}}).$$ (F.10)

Equations (F.9) and (F.10) proves (28). The expression (29) for the MBR point is directly obtained from Corollary 1 and Fig. 9.

Appendix G Proofs of Propositions

G-A Proof of Proposition 1

As in (A.23), capacity $\mathcal{C}$ for maximum $d_{I},d_{c}$ setting ($d_{I}=n_{I}-1,d_{c}=n-n_{I}$) is expressed as

$$\mathcal{C}=\displaystyle\min_{\bm{s}\in S,\bm{\pi}\in\Pi(\bm{s})}L(\bm{s},\bm{\pi})$$ (G.1)

where

$$L(\bm{s},\bm{\pi}) =\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(\bm{\pi})\},$$

$$\omega_{i}(\bm{\pi}) =\gamma-e_{i}(\bm{\pi})\beta_{I}-(i-1-e_{i}(\bm{\pi}))\beta_{c},$$ (G.2)

$$e_{i}(\bm{\pi}) =\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}},$$

as in (A.20), (A.21) and (A.19).

Consider a general $d_{I},d_{c}$ setting, where each newcomer node is helped by $d_{I}$ nodes in the same cluster, receiving $\beta_{I}$ information from each node, and $d_{c}$ nodes in other clusters, receiving $\beta_{c}$ information from each node. Under this setting, the coefficient of $\beta_{I}$ in (G.2) cannot exceed $d_{I}$. Similarly, the coefficient of $\beta_{c}$ in (G.2) cannot exceed $d_{c}$. Thus, the capacity for general $d_{I},d_{c}$ is expressed as

$$\mathcal{C}(d_{I},d_{c})=\displaystyle\min_{\bm{s}\in S,\bm{\pi}\in\Pi(\bm{s})}\ L(d_{I},d_{c},\bm{s},\bm{\pi})$$ (G.3)

where

$$L(d_{I},d_{c},\bm{s},\bm{\pi}) =\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(d_{I},d_{c},\bm{s},\bm{\pi})\},$$

$$\omega_{i}(d_{I},d_{c},\bm{s},\bm{\pi}) =\gamma-\min\{d_{I},e_{i}(\bm{\pi})\}\beta_{I}$$

$$\quad\quad-\min\{d_{c},i-1-e_{i}(\bm{\pi})\}\beta_{c},$$ (G.4)

$$e_{i}(\bm{\pi}) =\sum_{j=1}^{i-1}\mathds{1}_{\pi_{j}=\pi_{i}}.$$

Consider arbitrary fixed $\bm{s},\bm{\pi}$ and $d_{c}$. Since $\gamma$ and $\gamma_{c}=d_{c}\beta_{c}$ are fixed in the basic setting of Proposition 1, only $d_{I}$ and $\beta_{I}$ are variables in (G.4), while other parameters are constants. Then, (G.4) can be expressed as

$$\omega_{i}(d_{I},d_{c},\bm{s},\bm{\pi}) =C_{1}-\min\{d_{I},e_{i}(\bm{\pi})\}\beta_{I}$$

$$=C_{1}-\frac{\min\{d_{I},e_{i}(\bm{\pi})\}}{d_{I}}C_{2}$$ (G.5)

where $C_{1}=\gamma-\min\{d_{c},i-1-e_{i}(\bm{\pi})\}\beta_{c}$ and $C_{2}=\gamma_{I}=\gamma-\gamma_{c}$ are constants. Note that

$$\frac{\min\{d_{I},e_{i}(\bm{\pi})\}}{d_{I}}=\begin{cases}1,&\text{ if }d_{I}\leq e_{i}(\bm{\pi}),\\ \frac{e_{i}(\bm{\pi})}{d_{I}},&\text{ otherwise }\end{cases}$$ (G.6)

is a non-increasing function of $d_{I}$. Thus, $\omega_{i}(d_{I},d_{c},\bm{s},\bm{\pi})$ in (G.5) is a non-decreasing function of $d_{I}$ for arbitrary fixed $\bm{s},\bm{\pi},d_{c}$ and $i\in[k]$. Since the maximum $d_{I}$ value is $n_{I}-1$, we have

$$L(d_{I},d_{c},\bm{s},\bm{\pi}) =\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(d_{I},d_{c},\bm{s},\bm{\pi})\}$$

$$\leq\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(n_{I}-1,d_{c},\bm{s},\bm{\pi})\}$$

$$=L(n_{I}-1,d_{c},\bm{s},\bm{\pi})$$ (G.7)

for $d_{I}\in[n_{I}-1]$. In other words, for all $\bm{s},\bm{\pi},d_{c}$, we have

$$\underset{d_{I}\in[n_{I}-1]}{\arg\max}\ L(d_{I},d_{c},\bm{s},\bm{\pi})=n_{I}-1.$$

Similarly, for all $\bm{s},\bm{\pi},d_{I}$,

$$\underset{d_{c}\in[n-n_{I}]}{\arg\max}\ L(d_{I},d_{c},\bm{s},\bm{\pi})=n-n_{I}$$

holds. Therefore, for all $\bm{s},\bm{\pi}$,

$$\underset{[d_{I},d_{c}]}{\arg\max}\ L(d_{I},d_{c},\bm{s},\bm{\pi})=[n_{I}-1,n-n_{I}].$$ (G.8)

Let

$$[\bm{s}^{*},\bm{\pi}^{*}]=\underset{\bm{s}\in S,\bm{\pi}\in\Pi(\bm{s})}{\arg\min}\ \ L(n_{I}-1,n-n_{I},\bm{s},\bm{\pi}).$$ (G.9)

Then, from (G.3), (G.8) and (G.9),

$$\mathcal{C}(d_{I},d_{c}) =\displaystyle\min_{\bm{s}\in S,\bm{\pi}\in\Pi(\bm{s})}\ L(d_{I},d_{c},\bm{s},\bm{\pi})$$

$$\leq L(d_{I},d_{c},\bm{s}^{*},\bm{\pi}^{*})\leq L(n_{I}-1,n-n_{I},\bm{s}^{*},\bm{\pi}^{*})$$

$$=\displaystyle\min_{\bm{s}\in S,\bm{\pi}\in\Pi(\bm{s})}\ L(n_{I}-1,n-n_{I},\bm{s},\bm{\pi})$$

$$=\mathcal{C}(n_{I}-1,n-n_{I})$$ (G.10)

for all $d_{I}\in[n_{I}-1]$ and $d_{c}\in[n-n_{I}]$. Therefore, choosing $d_{I}=n_{I}-1$ and $d_{c}=n-n_{I}$ maximizes storage capacity when the available resources, $\gamma$ and $\gamma_{c}$, are given.

G-B Proof of Proposition 2

First, we prove (8). Recall $\rho_{i}$ and $g_{m}$ defined in (6) and (7). Consider the support set $S$, which is defined as

$$S=\{i\in[n_{I}]:g_{i}\geq 1\}.$$ (G.11)

Then, we have

$$\rho_{i}=n_{I}-i \leq n_{I}-1,$$ (G.12)

$$\sum_{m=1}^{i-1}g_{m} \geq i-1$$ (G.13)

for every $i\in S$. Therefore, by combining (G.13) and (6),

$$n-\rho_{i}-j-\sum_{m=1}^{i-1}g_{m} \leq n-(i-1)-j-\rho_{i}$$

$$=n-n_{I}-(j-1)\leq n-n_{I}$$ (G.14)

holds for every $i\in S,j\in[g_{i}]$. Combining (2), (G.12) and (G-B) results in

$$\rho_{i}\beta_{I}+(n-\rho_{i}-j-\sum_{m=1}^{i-1}g_{m})\beta_{c}\leq(n_{I}-1)\beta_{I}+(n-n_{I})\beta_{c}=\gamma$$ (G.15)

for arbitrary $i\in S,j\in[g_{i}]$. Since $[g_{i}]=\emptyset$ holds for $i\in[n_{I}]\setminus S$, we conclude that (G.15) holds for $(i,j)$ with $i\in[n_{I}]$, $j\in[g_{i}]$.

Second, we prove (9). Using $q$ and $r$ in (C.9) and (C.10),

$$g_{i}=\begin{cases}q+1,&i\leq r\\ q,&\text{otherwise}\end{cases}$$ (G.16)

Therefore, $\sum_{i=1}^{n_{I}}g_{i}=(q+1)r+q(n_{I}-r)=r+qn_{I}=k,$ where the last equality is from (C.11).

Appendix H Proofs of Lemmas

H-A Proof of Lemma 1

Using (2), $\underline{C}$ in (14) can be expressed as

$$\underline{C} =\frac{k}{2}\left((n_{I}-1)\beta_{I}+(n-n_{I})(1+\frac{n-k}{n(1-1/L)})\beta_{c}\right)$$

$$=\frac{k}{2}\left((n_{I}-1)\beta_{I}+(n-n_{I})(1+\frac{n-k}{n-n_{I}})\beta_{c}\right)$$

$$=\frac{k}{2}\left\{(n_{I}-1)\beta_{I}+(2n-n_{I}-k)\beta_{c}\right\}.$$ (H.1)

According to (A.20) and (A.68) in Appendix B, the capacity can be expressed as

$$\mathcal{C}=L(\bm{s}_{h},\bm{\pi}_{v})=\sum_{i=1}^{k}\min\{\alpha,\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))\}.$$ (H.2)

From (A.21), we have

$$\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))\leq\gamma$$ (H.3)

for $i\in[k]$. Therefore, when $\alpha=\gamma$, the capacity expression in (H.2) reduces to

$$\mathcal{C}=\sum_{i=1}^{k}\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h})).$$ (H.4)

Recall (A.64):

$$\omega_{i}(\bm{\pi}_{v}(\bm{s}_{h}))=(n_{I}-h_{i})\beta_{I}+(n-i-n_{I}+h_{i})\beta_{c}.$$ (H.5)

From the expression of $(h_{i})_{i=1}^{k}$ in (A.66), we have

$$\sum_{i=1}^{k}(n_{I}-h_{i})=\sum_{s=1}^{n_{I}}g_{s}(n_{I}-s)$$ (H.6)

since $\sum_{m=1}^{k}g_{m}=k$ from (9),

Using (H.5) and (H.6), the capacity expression in (H.4) is expressed as

$$\mathcal{C} =\left(\sum_{i=1}^{k}(n_{I}-h_{i})\right)\beta_{I}+\left(\sum_{i=1}^{k}(n-i-(n_{I}-h_{i}))\right)\beta_{c}$$

$$=A_{0}\beta_{I}+B_{0}\beta_{c}$$ (H.7)

where $A_{0}=\sum_{s=1}^{n_{I}}g_{s}(n_{I}-s)$ and

$$B_{0} =\sum_{i=1}^{k}(n-i)-A_{0}.$$ (H.8)

Similarly, $\underline{C}$ in (H.1) can be expressed as

$$\underline{C}=A_{0}^{\prime}\beta_{I}+B_{0}^{\prime}\beta_{c}$$ (H.9)

where $A_{0}^{\prime}=(n_{I}-1)\frac{k}{2}$ and

$$B_{0}^{\prime} =(2n-n_{I}-k)\frac{k}{2}=\sum_{i=1}^{k}(n-i)-A_{0}^{\prime}.$$ (H.10)

First, we show that $\mathcal{C}\geq\underline{C}$ holds. From (H-A), (H.8), (H.9) and (H.10),

$$\mathcal{C} -\underline{C}=(A_{0}-A_{0}^{\prime})\beta_{I}+(B_{0}-B_{0}^{\prime})\beta_{c}$$

$$=(A_{0}-A_{0}^{\prime})\beta_{I}-(A_{0}-A_{0}^{\prime})\beta_{c}=(A_{0}-A_{0}^{\prime})(\beta_{I}-\beta_{c}).$$ (H.11)

Since we consider the $\beta_{I}\geq\beta_{c}$ case, all we need to prove is

$$A_{0}-A_{0}^{\prime}\geq 0.$$

Using $(g_{i})_{i=1}^{k}$ expression in (G.16), $A_{0}$ can be rewritten as

$$A_{0} =\sum_{s=1}^{n_{I}}g_{s}(n_{I}-s)=q\sum_{s=1}^{n_{I}}(n_{I}-s)+\sum_{s=1}^{r}(n_{I}-s)$$

$$=q\frac{n_{I}(n_{I}-1)}{2}+\sum_{s=1}^{r}(n_{I}-s)$$

$$=q\frac{n_{I}(n_{I}-1)}{2}+\frac{r((n_{I}-1)+(n_{I}-r))}{2}$$

$$=\left(qn_{I}+r\right)\frac{n_{I}-1}{2}+\frac{r(n_{I}-r)}{2}$$

$$=\frac{k(n_{I}-1)}{2}+\frac{r(n_{I}-r)}{2}=A_{0}^{\prime}+\frac{r(n_{I}-r)}{2}.$$

Since $0\leq r<n_{I}$, we have

$$A_{0}-A_{0}^{\prime}=\frac{r(n_{I}-r)}{2}\geq 0.$$ (H.12)

Therefore, $\mathcal{C}\geq\underline{C}$ holds.

Second, we prove $\mathcal{C}\leq\underline{C}+n_{I}^{2}(\beta_{I}-\beta_{c})/8$. Note that $A_{0}-A_{0}^{\prime}$ in (H.12) is maximized when $r=\lfloor n_{I}/2\rfloor$ holds. Thus, $A_{0}-A_{0}^{\prime}\leq\frac{\lfloor n_{I}/2\rfloor(n_{I}-\lfloor n_{I}/2\rfloor)}{2}\leq n_{I}^{2}/8.$ Combining with (H-A),

$$\mathcal{C}-\underline{C} =(A_{0}-A_{0}^{\prime})(\beta_{I}-\beta_{c})\leq n_{I}^{2}(\beta_{I}-\beta_{c})/8.$$

H-B Proof of Lemma 2

Recall that $\xi=\gamma_{c}/\gamma,\gamma$ and $R=k/n$ value are all fixed. The expression for $\underline{C}$ in (14) can be expressed as

$$\underline{C} =\frac{k}{2}(\gamma+\frac{n-k}{n(1-\frac{1}{L})}\gamma_{c})=\frac{nR}{2}(\gamma+\frac{1-R}{1-\frac{1}{L}}\gamma_{c})$$

$$=\gamma\frac{nR}{2}(1+\frac{1-R}{(1-\frac{1}{L})}\xi)$$ (H.13)

Note that (H.13) is a monotonic decreasing function of $L$. Moreover, we consider the $L\geq 2$ case, as mentioned in (4). Thus, $\underline{C}$ is upper/lower bounded by expressions for $L=2$ and $L=\infty$, respectively:

$$\gamma\frac{nR}{2}(1+(1-R)\xi)<\underline{C}\leq\gamma\frac{nR}{2}(1+2(1-R)\xi).$$ (H.14)

Therefore, $\underline{C}=\Theta(n)$ holds. Moreover, the expression for $\delta$ in (17) is

$$\delta =\frac{n_{I}^{2}(\beta_{I}-\beta_{c})}{8}=\frac{n_{I}^{2}}{8}(\frac{\gamma_{I}}{n_{I}-1}-\frac{\gamma_{c}}{n-n_{I}})$$

$$=\frac{n_{I}^{2}}{8}(\frac{\gamma(1-\xi)}{n_{I}-1}-\frac{\gamma\xi}{n-n_{I}})$$

$$=\frac{n_{I}^{2}\gamma}{8}\frac{(1-\xi)(n-n_{I})-\xi(n_{I}-1)}{(n_{I}-1)(n-n_{I})}.$$ (H.15)

Putting $n=n_{I}L$ into (H.15), we get

$$\delta =\frac{n_{I}\gamma}{8}\frac{(1-\xi)n_{I}(L-1)-\xi(n_{I}-1)}{(n_{I}-1)(L-1)}=O(n_{I}).$$

Jy-yong Sohn (S’15) received the B.S. and M.S. degrees in electrical engineering from the Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea, in 2014 and 2016, respectively. He is currently pursuing the Ph.D. degree in KAIST. His research interests include coding for distributed storage and distributed computing, massive MIMO effects on wireless multi cellular system and 5G Communications. He is a recipient of the IEEE international conference on communications (ICC) best paper award in 2017.

Beongjun Choi (S’17) received the B.S. and M.S. degrees in mathematics and electrical engineering from the Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea, in 2014 and 2017. He is currently pursuing the electrical engineering Ph.D degree in KAIST. His research interests include error-correcting codes, distributed storage system and information theory. He is a co-recipient of the IEEE international conference on communications (ICC) best paper award in 2017.

Sung Whan Yoon (M’17) received the M.S. and Ph.D. degrees in electrical engineering from the Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea, in 2013 and 2017 respectively. He is currently a postdoctoral researcher in KAIST from 2017. His research interests are in the area of coding theory, distributed system and artificial intelligence, with focusing on polar codes, distributed storage system and meta-learning algorithm of neural network. Especially for the area of artificial intelligence, his primary interests include information theoretic analysis and algorithmic development of meta-learning. He was a co-recipient of the IEEE International Conference on Communications best Paper Award in 2017.

Jaekyun Moon (F’05) received the Ph.D degree in electrical and computer engineering at Carnegie Mellon University, Pittsburgh, Pa, USA. He is currently a Professor of electrical engineering at KAIST. From 1990 through early 2009, he was with the faculty of the Department of Electrical and Computer Engineering at the University of Minnesota, Twin Cities. He consulted as Chief Scientist for DSPG, Inc. from 2004 to 2007. He also worked as Chief Technology Officer at Link-A-Media Devices Corporation. His research interests are in the area of channel characterization, signal processing and coding for data storage and digital communication. Prof. Moon received the McKnight Land-Grant Professorship from the University of Minnesota. He received the IBM Faculty Development Awards as well as the IBM Partnership Awards. He was awarded the National Storage Industry Consortium (NSIC) Technical Achievement Award for the invention of the maximum transition run (MTR) code, a widely used error-control/modulation code in commercial storage systems. He served as Program Chair for the 1997 IEEE Magnetic Recording Conference. He is also Past Chair of the Signal Processing for Storage Technical Committee of the IEEE Communications Society. He served as a guest editor for the 2001 IEEE JSAC issue on Signal Processing for High Density Recording. He also served as an Editor for IEEE TRANSACTIONS ON MAGNETICS in the area of signal processing and coding for 2001-2006. He is an IEEE Fellow.